dp題，類似于01背包的轉移
需要注意的是：背包容量在有的時候可能為負數，所以需要算出最大數據量整體平移
像01背包一樣直接倒序循環j并不能保證每一個物品只選一個，兩個等價的物品在計算時可能會重復使用
所以把i（物品）放在最后一維，通過chk函數來檢查該物品此前是否已經選過，從而保證轉移的正確性
繼續鍛煉思維……

Code：

#include <cstdio> #include <algorithm> #include <cstring> using namespace std;const int N = 205; const int M = 25; const int MaxNum = 805;int testcase = 0, n, m, a[N], b[N], dp[M][MaxNum], path[M][MaxNum], tot, s[M];inline void read(int &X) {X = 0;char ch = 0;int op = 1;for(; ch > '9' || ch < '0'; ch = getchar())if(ch == '-') op = -1;for(; ch >= '0' && ch <= '9'; ch = getchar())X = (X << 3) + (X << 1) + ch - 48;X *= op; } void find(int j, int k) {if(j == 0) return;s[++tot] = path[j][k];find(j - 1, k - (a[path[j][k]] - b[path[j][k]])); }bool chk(int j, int k, int i) {if(j == 0) return 1;if(path[j][k] == i) return 0;return chk(j - 1, k - (a[path[j][k]] - b[path[j][k]]), i); }int main() {for(read(n), read(m); n + m != 0; read(n), read(m)) {testcase++;for(int i = 1; i <= n; i++)read(a[i]), read(b[i]);int fix = m * 20;memset(dp, 0xcf, sizeof(dp));memset(path, 0, sizeof(path));const int inf = -dp[0][0];dp[0][fix] = 0;/* for(int i = 1; i <= n; i++)for(int j = m; j >= 1; j--) for(int k = 0; k <= 800; k++) if(dp[j - 1][k - (a[i] - b[i])] != -inf) if(chk(j - 1, k - (a[i] - b[i]), i))if(dp[j - 1][k - (a[i] - b[i])] + (a[i] + b[i]) > dp[j][k]) {dp[j][k] = dp[j - 1][k - (a[i] - b[i])] + (a[i] + b[i]);path[j][k] = i;} */for(int j = 1; j <= m; j++)for(int k = 0; k <= 2 * fix; k++)if(dp[j - 1][k] >= 0) for(int i = 1; i <= n; i++)if(chk(j - 1, k, i) && dp[j - 1][k] + a[i] + b[i] > dp[j][k + (a[i] - b[i])]) {dp[j][k + (a[i] - b[i])] = dp[j - 1][k] + a[i] + b[i];path[j][k + (a[i] - b[i])] = i;} int ans;for(int i = 0; i <= fix; i++) {if(dp[m][fix + i] != -inf && dp[m][fix - i] == -inf) {ans = i;break;} else if(dp[m][fix - i] != -inf && dp[m][fix + i] == -inf) {ans = -i;break;} else if(dp[m][fix + i] != -inf && dp[m][fix - i] != -inf){if(dp[m][fix - i] > dp[m][fix + i]) ans = -i;else ans = i;break;}} tot = 0;find(m, fix + ans);sort(s + 1, s + m + 1);int ansp = 0, ansd = 0;for(int i = 1; i <= m; i++) {ansp += a[s[i]];ansd += b[s[i]];}printf("Jury #%d\n", testcase);printf("Best jury has value %d for prosecution and value %d for defence: \n", ansp, ansd);for(int i = 1; i <= m; i++)printf(" %d", s[i]);puts("\n");} return 0;

吐槽：sb輸出格式，defence：后面的空格坑死我了

轉載于:https://www.cnblogs.com/CzxingcHen/p/9466358.html

總結

以上是生活随笔為你收集整理的poj1015 Jury Compromise的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。