pku 1015 Jury Compromise DP

小咪咪 2022-07-12 10:15 106阅读 0赞

\#include <iostream> \#include <cstdio> \#include <cstring> \#include <exception> using namespace std; \#define BASE 400 int opt\[202\]\[22\]\[802\]; int arr1\[202\], arr2\[202\]; int ret\[22\]; void findPath(int n,int m, int delta) \{ int i = n, j = m; while(i >= 1 && j >= 1) \{ if(opt\[i-1\]\[j\]\[BASE+delta\] == opt\[i\]\[j\]\[BASE+delta\]) i--; else \{ delta -= arr1\[i\]-arr2\[i\]; ret\[j\] = i; i--, j--; \} \} \} int main() \{ int n, m; int cnt = 0; while (scanf("%d%d", &n, &m) && n) \{ for(int i = 1; i <= n; ++i) scanf("%d%d", &arr1\[i\], &arr2\[i\]); int scope = m\*20; memset(opt, -1, sizeof(opt)); for(int i = 1; i <= n; ++i) opt\[i\]\[0\]\[BASE\] = 0; opt\[1\]\[1\]\[BASE+arr1\[1\]-arr2\[1\]\] = arr1\[1\]+arr2\[1\]; for(int i = 2; i <= n; ++i) for(int j = 1; j <= m; ++j) for (int k = -scope; k <= scope; ++k) \{ if(j <= i) \{ if(j <= i-1) \{ int v = BASE+k-(arr1\[i\]-arr2\[i\]); if(v >= BASE-scope && v <= BASE+scope) \{ if(opt\[i-1\]\[j-1\]\[v\] != -1) opt\[i\]\[j\]\[BASE+k\] = max(opt\[i\]\[j\]\[BASE+k\], opt\[i-1\]\[j-1\]\[v\]+arr1\[i\]+arr2\[i\]); if(opt\[i-1\]\[j\]\[BASE+k\] != -1) opt\[i\]\[j\]\[BASE+k\] = max(opt\[i\]\[j\]\[BASE+k\], opt\[i-1\]\[j\]\[BASE+k\]); \} else \{ if(opt\[i-1\]\[j\]\[BASE+k\] != -1) opt\[i\]\[j\]\[BASE+k\] = max(opt\[i\]\[j\]\[BASE+k\], opt\[i-1\]\[j\]\[BASE+k\]); \} \} else \{ int v = BASE+k-(arr1\[i\]-arr2\[i\]); if(v >= BASE-scope && v <= BASE+scope) \{ if(opt\[i-1\]\[j-1\]\[v\] != -1) opt\[i\]\[j\]\[BASE+k\] = max(opt\[i\]\[j\]\[BASE+k\], opt\[i-1\]\[j-1\]\[v\]+arr1\[i\]+arr2\[i\]); \} \} \} \} int delta = 0; for(int i = 0; i <= scope; ++i) \{ if(opt\[n\]\[m\]\[BASE+i\] != -1) \{ if(opt\[n\]\[m\]\[BASE-i\] == -1) delta = i; else \{ if(opt\[n\]\[m\]\[BASE+i\] > opt\[n\]\[m\]\[BASE-i\]) delta = i; else delta = -i; \} break; \} else if(opt\[n\]\[m\]\[BASE-i\] != -1) \{ delta = -i; break; \} \} findPath(n, m, delta); int sum1 = 0, sum2 = 0; for(int i = 1; i <= m; ++i) sum1 += arr1\[ret\[i\]\], sum2 += arr2\[ret\[i\]\]; printf("Jury \#%d/nBest jury has value %d for prosecution and value %d for defence:/n", ++cnt, sum1, sum2); for(int i = 1; i <= m; ++i) printf(" %d", ret\[i\]); printf("/n/n"); \} return 0; \}

下面附一份我AC之前的一份丑陋的WA代码, 开始没有考虑全面, 状态有后效应, 需增加状态转移的维数来消除后效应.

//WA代码!! \#include <iostream> \#include <cmath> using namespace std; int delta\[205\]\[25\]; int sum1\[205\]\[25\], sum2\[205\]\[25\]; bool record\[205\]\[25\]; int arr1\[205\],arr2\[205\]; int ret\[205\]; int i, j; int main() \{ int n, m; int cnt = 0; while(scanf("%d%d", &n, &m) && n) \{ for(i = 1; i <= n; ++i) scanf("%d%d", &arr1\[i\], &arr2\[i\]); delta\[1\]\[0\] = 0; sum1\[1\]\[0\] = 0, sum2\[1\]\[0\] = 0; record\[1\]\[0\] = false; delta\[1\]\[1\] = arr1\[1\]-arr2\[1\]; sum1\[1\]\[1\] = arr1\[1\], sum2\[1\]\[1\] = arr2\[1\]; record\[1\]\[1\] = true; for(i = 2; i <= n; ++i) for(j = 0; j <= m; ++j) if(j <= i) \{ if(j <= i-1) \{ if(abs(delta\[i-1\]\[j\]) > abs(delta\[i-1\]\[j-1\]+arr1\[i\]-arr2\[i\])) \{ delta\[i\]\[j\] = delta\[i-1\]\[j-1\]+arr1\[i\]-arr2\[i\]; sum1\[i\]\[j\] = sum1\[i-1\]\[j-1\]+arr1\[i\], sum2\[i\]\[j\] = sum2\[i-1\]\[j-1\]+arr2\[i\]; record\[i\]\[j\] = true; \} else if(abs(delta\[i-1\]\[j\]) < abs(delta\[i-1\]\[j-1\]+arr1\[i\]-arr2\[i\])) \{ delta\[i\]\[j\] = delta\[i-1\]\[j\]; sum1\[i\]\[j\] = sum1\[i-1\]\[j\], sum2\[i\]\[j\] = sum2\[i-1\]\[j\]; record\[i\]\[j\] = false; \} else \{ if(sum1\[i-1\]\[j\]+sum2\[i-1\]\[j\] <= sum1\[i-1\]\[j-1\]+arr1\[i\]+sum2\[i-1\]\[j-1\]+arr2\[i\]) \{ delta\[i\]\[j\] = delta\[i-1\]\[j-1\]+arr1\[i\]-arr2\[i\]; sum1\[i\]\[j\] = sum1\[i-1\]\[j-1\]+arr1\[i\], sum2\[i\]\[j\] = sum2\[i-1\]\[j-1\]+arr2\[i\]; record\[i\]\[j\] = true; \} else \{ delta\[i\]\[j\] = delta\[i-1\]\[j\]; sum1\[i\]\[j\] = sum1\[i-1\]\[j\], sum2\[i\]\[j\] = sum2\[i-1\]\[j\]; record\[i\]\[j\] = false; \} \} \} else \{ delta\[i\]\[j\] = delta\[i-1\]\[j-1\]+arr1\[i\]-arr2\[i\]; sum1\[i\]\[j\] = sum1\[i-1\]\[j-1\]+arr1\[i\], sum2\[i\]\[j\] = sum2\[i-1\]\[j-1\]+arr2\[i\]; record\[i\]\[j\] = true; \} \} cout << "delta: " << delta\[n\]\[m\] << endl; i = n; j = m; int num = 1; while(i >= 1 && j >= 0) \{ if(record\[i\]\[j\]) \{ ret\[num++\] = i; i--, j--; \} else i--; \} int sum1 = 0, sum2 = 0; for(i = 1; i <= m; ++i) \{ sum1 += arr1\[ret\[i\]\]; sum2 += arr2\[ret\[i\]\]; \} printf("Jury \#%d/nBest jury has value %d for prosecution and value %d for defence:/n", ++cnt, sum1, sum2); for(i = m; i >= 1; --i) printf(" %d", ret\[i\]); printf("/n/n"); \} return 0; \}