yuan chuang?? ? ? ? ? ?

題意：有n個(gè)科目的作業(yè)，每個(gè)任務(wù)都有截止日期和完成時(shí)間，完成所有任務(wù)，如果超過一天，則扣一分；問你完成任務(wù)扣的最少分?jǐn)?shù)，

并且輸出完成任務(wù)的順序；注：在某一個(gè)任務(wù)超期時(shí)，另一個(gè)任務(wù)也在超期

二進(jìn)制壓縮枚舉各個(gè)狀態(tài)

#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;} }

總結(jié)

以上是生活随笔為你收集整理的hdu-1074 Doing Homework的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。