2009年12月8日星期二.sgu482
sgu482:dp
題目解釋：n個(gè)木條，高h(yuǎn)[1...n],要求拿走盡量多的木條，同時(shí)保證此時(shí)剩下的所有木條的周長(zhǎng)
不小于原來(lái)的一半
從反面思考,題目要求求能拿走的最大面積，按照周長(zhǎng)dp沒(méi)有辦法。搜是肯定不行的，可以按照
面積dp，面積最大才5000。
我們可以求出每個(gè)面積的最大周長(zhǎng)，遍歷一下找符合條件的最小面積，然后用原面積減這個(gè)面積
即是所求。
現(xiàn)在考慮求周長(zhǎng)的問(wèn)題
如果后一個(gè)比上一個(gè)短 周長(zhǎng) += 2 ;
| | || |如果后一個(gè)比上一個(gè)長(zhǎng) 周長(zhǎng) += 2 + 2 * abs(h[i]-h[i-1]);
|| || |但是如果按照如上的思路，肯定會(huì)寫(xiě)出一個(gè)2維dp，例如
area[i] 表示面積為i時(shí)的最大周長(zhǎng)
1
2 for(i = 1;i <= n;i++) {
3 for(s = h[i];s <= 5000;s++) {
4 if(area[s-h[i]] >= 0 ) {
5 if (area[s] < area[s-h[i]] + cacu(h[i],last[s-h[i]])) {
6 area[s] = area[s-h[i]] + cacu(h[i],last[s-h[i]]));
7 last[s] = h[i];
8 }
9 }
10 }
11 }
但是這樣寫(xiě)是錯(cuò)的.... 我一開(kāi)始就是這么寫(xiě)的 WA at test case 13
∵ 當(dāng)前面積的<<<更大周長(zhǎng)并不能保證更大面積得到更好的解>>>,周長(zhǎng)只和高度的差有關(guān)
<<<也就是二維dp并不具有最優(yōu)子結(jié)構(gòu)>>>
∴ 要寫(xiě)成三維dp
dp[i][j]表示面積為i時(shí)使用前j個(gè)木條的周長(zhǎng)最大值
如下方法能求出最優(yōu)解
1 for(i = 1;i <= n;i++) {
2 for(s = h[i];s < N;s++) {
3 for(j = i - 1;j >= 0;j --) {
4 if(dp[s-h[i]][j] >= 0) {
5 if (dp[s][i] < dp[s-h[i]][j] + cacu(h[i],h[j])) {
6 dp[s][i] = dp[s-h[i]][j] + cacu(h[i],h[j]);
7 }
8 }
9 }
10 }
11 }
==========貼代碼====================華麗麗的分割線====================
1 /*
2 * SOUR:sug482
3 * ALGO:dp
4 * DATE: 2009年 12月 05日 星期六 13:19:59 CST
5 * COMM:3~4
6 * 從反面思考
7 * */
8 #include<iostream>
9 #include<cstdio>
10 #include<cstdlib>
11 #include<cstring>
12 #include<algorithm>
13 using namespace std;
14 typedef long long LL;
15 const int maxint = 0x7fffffff;
16 const long long max64 = 0x7fffffffffffffffll;
17 const int N = 5010;
18 const int inf = 1 << 28;
19 int n;
20 int dp[N][128],pre[N][128][2],h[N],perimeter,area,res,out[N],top,vis[128];
21 int cacu(int h, int last) { return h-last+abs(h-last)+2; }
22
23 int main()
24 {
25 int i,j,k,s,x,y;
26 scanf("%d",&n);
27 h[0] = 0,perimeter = 0,area = 0,res = 0;
28 for(i = 1;i <= n;i++) {
29 scanf("%d",h + i);
30 perimeter += cacu(h[i],h[i-1]);
31 area += h[i];
32 }
33 for(i = 0;i < N;i++) {dp[0][i] = 0;}
34 for(i = 1;i < N;i++) {
35 for(j = 0;j < N;j++) {
36 dp[i][j] = -1;
37 }
38 }
39 for(i = 1;i <= n;i++) {
40 for(s = h[i];s < N;s++) {
41 for(j = i - 1;j >= 0;j --) {
42 if(dp[s-h[i]][j] >= 0) {
43 if (dp[s][i] < dp[s-h[i]][j] + cacu(h[i],h[j])) {
44 dp[s][i] = dp[s-h[i]][j] + cacu(h[i],h[j]);
45 pre[s][i][0] = s - h[i];
46 pre[s][i][1] = j;
47 }
48 }
49 }
50 if(dp[s][i] + dp[s][i] >= perimeter) {
51 if (res < area - s) {
52 res = area - s;
53 x = s,y = i;
54 }
55 }
56 }
57 }
58 printf("%d\n",res);
59 if(res > 0) {
60 while(x != 0 && y != 0) {
61 vis[y] = 1;
62 int tx = pre[x][y][0];
63 int ty = pre[x][y][1];
64 x = tx,y = ty;
65 }
66 for(i = 1;i <= n;i++) {
67 if(!vis[i]) {
68 out[top++] = i;
69 }
70 }
71 }
72 printf("%d\n",top);
73 if(top > 0)
74 printf("%d",out[0]);
75 for(i = 1;i < top;i++) {
76 printf(" %d",out[i]);
77 }
78 if(top > 0)
79 putchar(10);
80 return 0;
81 }
82