本文共 1906 字,大约阅读时间需要 6 分钟。
题意:有n个科目的作业,每个任务都有截止日期和完成时间,完成所有任务,如果超过一天,则扣一分;问你完成任务扣的最少分数,
并且输出完成任务的顺序;注:在某一个任务超期时,另一个任务也在超期
二进制压缩枚举各个状态
#include#include #include #include 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< > 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] <
zoj - 2297 与上题类似,处理得过程中判断特殊的情况
题意:武士打怪,打完小怪之后,再打boss,在打的过程中如果HP小于ai则你就挂了,or 你可以得到bi的HP,问你能否打完小怪之后,还能不能把boss打败。
#include#include #include #include #include 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!!!"<
转载地址:http://ydsgi.baihongyu.com/