posts - 12,  comments - 40,  trackbacks - 0
http://acm.pku.edu.cn/JudgeOnline/problem?id=3351
Gerrymandering
难!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>? a:b;}
15 void input() {
16     scanf("%d"&n);
17     scanf("%d"&p);
18     int i, j, k;
19     memset(v[0], 0sizeof(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 阅读(1685) 评论(8)  编辑 收藏 引用 所属分类: 动态规划

FeedBack:
# re: 动态规划题集锦
2007-08-22 17:32 | oyjpart
LSM太猛了!
呵呵
赞~  回复  更多评论
  
# re: 动态规划题集锦
2007-08-22 17:47 | gaosimeng
不错  回复  更多评论
  
# re: POJ 3351 —— Gerrymandering
2007-09-04 13:39 | acmer
看不懂啊 真郁闷  回复  更多评论
  
# re: POJ 3351 —— Gerrymandering
2007-12-07 14:19 | Ctas
这题是求参加合并的选区数最少值,还是要求合并次数最少值??
PKU上好像是求参加合并的选区数最少值,“gives the minimum number of ridings that need to be merged in order for the first party to win a majority of ridings.”
按照作者写的,“dp[k][t]代表前k个riding合并成t块(也就是说合并k-t次),目标则是max(t)”,好像是求合并次数最少值???  回复  更多评论
  
# re: POJ 3351 —— Gerrymandering
2007-12-21 00:19 | smcdfneg
5
5
3 5 6 7 9
4 1 1 5 5
2 5 3 3 8
2 4 2 2 1
9 3 2 5 5
4
这个数据是有错的吧!  回复  更多评论
  
# re: POJ 3351 —— Gerrymandering
2010-03-16 15:27 | 发生的范德萨
程序没注释,要看懂比较麻烦!  回复  更多评论
  
# re: POJ 3351 —— Gerrymandering
2014-07-28 15:18 | 杨哂
我用了一个 几乎是O(n) 的算法 写了一个 下界的估价函数, 然后二维dp+上下界剪枝,跑官方数据秒出(n<=10^5),然后测了一下估价函数,结果,对所有官方数据,估价函数就是答案。。。。。。也就是直接用 O(n)的做法就能得到正确答案。。。
  回复  更多评论
  
# re: POJ 3351 —— Gerrymandering
2014-07-28 15:19 | 杨哂
@杨哂
但是 理论上貌似估价函数 作为最后的答案应该是不正确的,不过数据比较难构造。。。。  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿(4)

随笔分类

随笔档案

牛牛 ACM/ICPC

最新随笔

搜索

  •  

最新随笔

最新评论

阅读排行榜

评论排行榜