【ASC 23】G. ACdream 1429 Rectangular Polygon --DP

题意:有很多棍子,从棍子中选出两个棍子集合,使他们的和相等,求能取得的最多棍子数。

解法:容易看出有一个多阶段决策的过程,对于每个棍子,我们有 可以不选,或是选在第一个集合,或是选在第二个集合 这三种决策。因为两个集合最后的和要相等,那么令一个集合为正,另一个为负,那么最后和为0,我们用偏移0的量来作为状态之一。

dp[i][j]表示前 i 个 偏移量为 j 的最大棍子数,因为每根棍最长为200,所以偏移量最多为+-20000,所以在+-20000之间枚举,最多100*40000

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
#define N 30007 int dp[][],path[][];
int a[]; int main()
{
freopen("polygon.in","r",stdin);
freopen("polygon.out","w",stdout);
int n,i,j;
while(scanf("%d",&n)!=EOF)
{
memset(dp,-,sizeof(dp));
int sum = ;
for(i=;i<=n;i++) {
scanf("%d",&a[i]);
sum += a[i];
}
int low = N-sum, high = N+sum;
dp[][N] = ;
for(i=;i<=n;i++) {
for(j=low;j<=high;j++) {
if(dp[i-][j] != - && dp[i][j] < dp[i-][j]) {
dp[i][j] = dp[i-][j];
path[i][j] = j;
}
if(dp[i-][j-a[i]] != - && dp[i][j] < dp[i-][j-a[i]]+) {
dp[i][j] = dp[i-][j-a[i]]+;
path[i][j] = j-a[i];
}
if(dp[i-][j+a[i]] != - && dp[i][j] < dp[i-][j+a[i]]+) {
dp[i][j] = dp[i-][j+a[i]]+;
path[i][j] = j+a[i];
}
}
}
printf("%d\n",dp[n][N]);
int now = N,pre;
vector<int> UP,DOWN;
for(i=n;i>=;i--) {
pre = path[i][now];
if(now > pre) UP.push_back(now-pre);
if(pre > now) DOWN.push_back(pre-now);
now = pre;
}
int x = , y = ;
for(i=;i<UP.size();i++) {
printf("%d %d\n",x,y);
x += UP[i];
printf("%d %d\n",x,y);
y++;
}
for(i=;i<DOWN.size();i++) {
printf("%d %d\n",x,y);
x -= DOWN[i];
printf("%d %d\n",x,y);
y++;
}
}
return ;
}
上一篇:[福大软工] Z班 团队Beta阶段成绩汇总


下一篇:深入理解HTTP协议