首页 > 代码库 > BZOJ2708 [Violet 1]木偶
BZOJ2708 [Violet 1]木偶
首先想到的是贪心。。。肯定不对嘛。。。T T
然后发现其实是可以DP的。。。不过我们要先排序
令f[i]表示前i个木偶最坏要丢掉几个，则
f[i] = max(f[j] + calc(j + 1, i)) 其中 j < i
而calc(x, y)函数计算从第x个到第y个木偶匹配最多可以丢掉几个，方法是：
hzwer："枚举可以扔掉的数量k，判断剩下的能否相互匹配，不能返回k-1
以及被扔掉的能否相互匹配，能匹配返回k-1"
1 /************************************************************** 2 Problem: 2708 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:24 ms 7 Memory:804 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <cstring>12 #include <algorithm>13 14 using namespace std;15 const int N = 55;16 int n, a[N], f[N];17 18 inline int read(){19 int x = 0, sgn = 1;20 char ch = getchar();21 while (ch < ‘0‘ || ch > ‘9‘){22 if (ch == ‘-‘) sgn = -1;23 ch = getchar();24 }25 while (ch >= ‘0‘ && ch <= ‘9‘){26 x = x * 10 + ch - ‘0‘;27 ch = getchar();28 }29 return sgn * x;30 }31 32 int calc(int x, int y){33 int i, k;34 for (k = 1; k <= y - x + 1; ++k){35 for (i = k; i <= y - x; ++i)36 if (abs(a[i + x] - a[i + x - k]) > 1) return k - 1;37 if (abs(a[x + k - 1] - a[y - k + 1]) <= 1) return k - 1;38 }39 return y - x + 1;40 }41 42 int main(){43 int i, j;44 while (scanf("%d", &n) != EOF){45 for (i = 1; i <= n; ++i)46 scanf("%d", a + i);47 sort(a + 1, a + n + 1);48 memset(f, 0, sizeof(f));49 for (i = 1; i <= n; ++i)50 for (j = 0; j < i; ++j)51 f[i] = max(f[i], f[j] + calc(j + 1, i));52 printf("%d\n", f[n]);53 }54 return 0;55 }
BZOJ2708 [Violet 1]木偶
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。