题目链接:
巨恶心。找了一晚上bug,发现for循环初始化居然不能代替memset。真心不服、
附AC代码:
1 #include2 #include 3 #include 4 using namespace std; 5 6 #define N 16 7 #define M 1<<16 8 #define inf 0x3f 9 int n, m;10 int dp[M], pre[M], t[M];11 int dead[N], cost[N];12 char name[N][210];13 14 void print(int t) {15 if (t == 0) return;16 print(pre[t]);17 t -= pre[t]; //18 for (int i=0; i t[i] ? 0 : t[i] - dead[j];50 if (dp[k] + tcost <= dp[i]) { //从前往后枚举的,应该是没有等于号会是字典序从小到大啊。???51 dp[i] = dp[k] + tcost;52 pre[i] = k;53 }54 }55 }56 printf("%d\n", dp[m-1]);57 print(m-1);58 }59 return 0;60 }
附详解代码:
1 /* 2 题意:给出n(1<=n<=15)个作业,和该作业的dealline 和 完成所需时间。作业晚交一天就会扣1分。 3 要知道完成所有任务使减少的分数最少的完成方案。如果方案数有多个,输出字典序最小的。作业名称长度不会超过100个字符。 4 5 //思路:从当前时间为0开始,寻找最紧迫的作为下一个要完成的目标,直到所有的任务完成。 6 当前最需要完成的应该是dealine-tasktime当前时间差最少的。也就是可以按照deadine-tasktime,从小到大排序。依次完成。 7 //以上出自无厘头。虽然也并没有验证这样为什么不对、 8 9 思路:状压DP。因为N最大是15.所以用一个数m,2^15表示总的状态。变成二进制时0和1分别表示当前作业没做和做了。从0到m的每一个状态,10 遍历每一个作业在当前状态下是否已经完成,如果没有,继续下一个作业。否则,比较当前状态没有完成该作业到完成该作业减少的时间和原来需要的时间,取最小值。11 dp[i] = j。表示i状态下减少时间最少是j。T_T说不清楚。具体见代码吧。。12 */13 14 #include15 #include 16 #include 17 using namespace std;18 19 const int N = 16, M = 1 << N;20 21 int d[N], c[N], n;22 int dp[M], pre[M], t[M];23 char s[N][105];24 25 void print(int k)26 {27 if(k == 0) return;28 print(pre[k]);29 k -= pre[k];30 for(int i = 0; i < n; ++i)31 if(k & 1 << i) puts(s[i]);32 }33 34 int main() {35 int T, m, cost;36 scanf("%d", &T);37 while(T--) {38 scanf("%d", &n);39 for (int i=0; i << n; // 0到m 表示所有的状态46 47 for (int i=1; i d[j] ? t[i] - d[j] : 0; //和j作业的截止时间对比,得出当前减少的时间54 if (dp[k] + cost <= dp[i]) { //判断是不是要从k到i。55 dp[i] = dp[k] + cost;56 pre[i] = k;57 }58 }59 }60 printf("%d\n", dp[m-1]);61 print(m-1);62 }63 return 0;64 }