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 閱讀(1812)
評論(8) 編輯 收藏 引用 所屬分類:
動態規劃