2009年12月8日星期二.sgu482
sgu482:dp
题目解释：n个木条，高h[1...n],要求拿走尽量多的木条，同时保证此时剩下的所有木条的周长
不小于原来的一半
从反面思考,题目要求求能拿走的最大面积，按照周长dp没有办法。搜是肯定不行的，可以按照
面积dp，面积最大才5000。
我们可以求出每个面积的最大周长，遍历一下找符合条件的最小面积，然后用原面积减这个面积
即是所求。
现在考虑求周长的问题
如果后一个比上一个短 周长 += 2 ;
| | || |如果后一个比上一个长 周长 += 2 + 2 * abs(h[i]-h[i-1]);
|| || |但是如果按照如上的思路，肯定会写出一个2维dp，例如
area[i] 表示面积为i时的最大周长
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 }
但是这样写是错的.... 我一开始就是这么写的 WA at test case 13
∵ 当前面积的<<<更大周长并不能保证更大面积得到更好的解>>>,周长只和高度的差有关
<<<也就是二维dp并不具有最优子结构>>>
∴ 要写成三维dp
dp[i][j]表示面积为i时使用前j个木条的周长最大值
如下方法能求出最优解
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