http://acm.pku.edu.cn/JudgeOnline/problem?id=3351Gerrymandering 难！O(n^3)的dp，降为接近O(n^2)才能过。
不难想到O(n^3)的dp，dp[k][t]代表前k个riding合并成t块（也就是说合并k-t次），所能取得的最大值（赢的riding个数减去输的riding个数）。定义w[i][j]代表i至j合并一起后的输赢状态，1或-1。
1、dp[0][0] = 0，状态转移方程dp[k][t] = max(dp[k'][t-1] + win[k'+1][k]), 0<=k'<k。
2、目标则是max(t) 使得dp[n][t] > 0，输出答案n-t。
转移的复杂度是o(n)，这样我们的复杂度就是O(n^3)，必须降低复杂度。
想法：我们求dp[k][t]时，遍历了一次dp[k'][t-1]，当我们再求dp[k+1][t]时，还需要再遍历一次dp[k'][t-1]，只不过这个时候k'范围增加了1。那我们能否在求dp[k][t]遍历dp[k'][t-1]时把这些有用信息记录下来供求dp[k+1][t]时用呢？
看状态转移方程：dp[k][t] = max(dp[k'][t-1] + win[k'+1][k])
问题：受win[k'+1][k]影响，dp[k'][t-1] 的最大值，加上win[k'+1][k]后并不一定是dp[k][t]的最大值
但是：仔细看会发现，win[k'+1][k]仅有两种取值，1和-1,而且当k'变化时dp[k'][t-1]的值相差2、4、6
这样的话，方程可以写成：dp[k][t] = maxdp + win[k''+1][k]，这里maxdp = max(dp[k'][t-1])，k''有一个限制，就是，dp[k''][t-1]必须等于maxdp。
一旦转换成这类方程后，dp[k'][t-1]的信息就可以重复利用，状态转移的复杂度大大降低。
实现：记录maxdp，然后建一个list，记录满足dp[k''][t-1] = maxdp的k'’，实时更新list，每次只需从list里转移状态就行。
优化：一旦从list里找到一个k''，满足win[k''+1][k]=1，那么dp[k][t] = maxdp + 1，dp[k][t]的计算就可马上结束。
1 //POJ_3351 ～ alpc02
2 #include <algorithm>
3 using namespace std;
4
5 const int INF = 12345678;
6 const int N = 1010;
7 const int P = 12;
8
9 int n, p;
10 int v[N][P];
11 int win[N][N];
12 int dp[N][N];
13
14 int Max(int a,int b){return a>b ? a:b;}
15 void input() {
16 scanf("%d", &n);
17 scanf("%d", &p);
18 int i, j, k;
19 memset(v[0], 0, sizeof(v[0]));
20 for(i=1; i<=n; i++)
21 for(j=1; j<=p; j++) {
22 scanf("%d", &k);
23 v[i][j] = v[i-1][j] + k;
24 }
25 }
26 void init() {
27 int i, j, k, vote;
28 for(i=1; i<=n; i++)
29 for(j=i; j<=n; j++) {
30 vote = v[j][1] - v[i-1][1];
31 for(k=2; k<=p; k++)
32 if(v[j][k] - v[i-1][k] >= vote)
33 break;
34 if(k > p) win[i][j] = 1;
35 else win[i][j] = -1;
36 }
37 }
38 int solve() {
39 init();
40
41 int i, j, k, t;
42 int list[N], top, mx;
43 dp[0][0] = 0;
44 for(j=1; j<=n; j++) {
45 top = 0;
46 mx = -INF;
47 for(i=j; i<=n; i++) {
48 if(dp[i-1][j-1] > mx) {
49 mx = dp[i-1][j-1];
50 list[0] = i-1;
51 top = 1;
52 }
53 else if(dp[i-1][j-1] == mx)
54 list[top++] = i-1;
55 for(t=0; t<top-1; t++)
56 if(win[list[t]+1][i] == 1)
57 break;
58 dp[i][j] = mx + win[list[t]+1][i];
59 }
60 }
61
62 int ans;
63 for(ans=n; ans>=1; ans--)
64 if(dp[n][ans] > 0)
65 return n-ans;
66 return -1;
67 }
68 int main() {
69 input();
70 printf("%d\n", solve());
71 return 0;
72 }
posted on 2007-08-22 11:30
LSM 阅读(1745)
评论(8) 编辑 收藏 引用 所属分类:
动态规划