hdu-1074 Doing Homework

yuan chuang            

题意：有n个科目的作业，每个任务都有截止日期和完成时间，完成所有任务，如果超过一天，则扣一分；问你完成任务扣的最少分数，

并且输出完成任务的顺序；注：在某一个任务超期时，另一个任务也在超期

二进制压缩枚举各个状态

#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> using namespace std; const int M = (1<<15)+3; char str[20][20]; int dp[M],pre[M],d[M],f[M],t[M]; void output(int x){if(!x) return ;output(x-(1<<pre[x]));cout << str[pre[x]] << endl; } int main(){int T,n;cin >> T;while(T --){cin >> n;for(int i = 0;i < n;i ++){cin >> str[i] >> d[i] >> f[i];};int cnt = 1 << n;for(int i = 1;i < cnt;i ++ ){dp[i] = 121321312;for(int j = n-1;j >= 0;j --){int k = 1 << j;if(!(k&i)) continue;int temp = t[i-k] + f[j] - d[j];if(temp < 0) temp = 0;if(dp[i] > dp[i-k] + temp){dp[i] = dp[i-k] + temp;t[i] = t[i-k] + f[j];pre[i] = j;}}}cout << dp[cnt-1] <<endl;output(cnt-1);} }

zoj - 2297 与上题类似，处理得过程中判断特殊的情况

题意：武士打怪，打完小怪之后，再打boss，在打的过程中如果HP小于ai则你就挂了，or 你可以得到bi的HP，问你能否打完小怪之后，还能不能把boss打败。

#include<cstdio> #include<cmath> #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int M = (1 << 20); int a[25],b[25]; int p[M],dp[M]; int main(){int n,m;while(cin >> n){for(int i = 0;i < n-1;i++)cin >> a[i] >> b[i];cin >> m;memset(dp,0,sizeof(dp));dp[0] = 100;int cnt = 1 <<(n-1) ;for(int i = 0;i < cnt;i++){for(int j = n-2;j >= 0;j --){int k = 1 << j;if(!(i&k)) continue;if(dp[i-k] >= a[j]) {if(dp[i] < dp[i - k] - a[j] + b[j]){dp[i] = min(dp[i-k] - a[j] + b[j],100);}}}}if(dp[cnt - 1] >= m) cout << "clear!!!"<<endl;else cout << "try again" << endl;} }

总结

以上是生活随笔为你收集整理的hdu-1074 Doing Homework的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。