| Time Limit: 1000MS | Memory Limit: 256000KB | 64bit IO Format: %lld & %llu |
Description
A rectangular polygon is a polygon whose edges are all parallel to the coordinate axes. The polygon must have a single, non-intersecting boundary. No two adjacent sides must be parallel.
Johnny has several sticks of various lengths. He would like to construct a rectangular polygon. He is planning to use sticks as horizontal edges of the polygon, and draw vertical edges with a pen.
Now Johnny wonders, how many sticks he can use. Help him, find the maximal number of sticks that Johnny can use. He will use sticks only as horizontal edges.
题目描述有些绕。总之就是摆一个直角多边形，横边全用木棍摆，竖边用线画（竖边可以无视），询问最多可用的木棍数量和具体摆法（摆法很多，任意输出一种）
Input
Output
. If no polygon can be constructed, output l = 0.
Sample Input
4
1 2 3 5
4
1 2 4 8
4
1 1 1 1
Sample Output
3
0 0
1 0
1 1
3 1
3 2
0 2
0
4
0 0
1 0
1 1
2 1
2 -2
1 -2
1 -1
0 -1
Hint
单组数据
In the first example Johnny uses a stick of length 1 for (0, 0)−(1, 0) edge, a stick of length 2 for (1, 1)−(3, 1) edge and a stick of length 3 for (3, 2) − (0, 2) edge. There is no way to use all four sticks.
Source
第一问：求最多使用木棍数量。竖边可以无视，问题简化成从所有木棍中挑出一部分，分成总长度相等的两组，求最大总长度。动规可解。
第二问：具体摆法。由于是多解任意输出一解，竖边依旧可以无视。在之前的动规中保存一下每次用的木棍长度（我保存的是端点间相对位置），最后输出就行。
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int q=;
const int mxn=;
const int bas=;
int le,ri;
int a[mxn];
int dp[mxn][bas*],p[mxn][bas*];
int n;
int st1[mxn],tp1;
int st2[mxn],tp2; int main(){
while(scanf("%d",&n)!=EOF){
memset(dp,-,sizeof(dp));
memset(p,,sizeof(p));
int i,j;
le=ri=bas;
for(i=;i<=n;i++)scanf("%d",&a[i]);
dp[][bas]=;
p[][bas]=bas;
for(i=;i<=n;i++){
for(j=le;j<=ri;j++){//枚举长度差
if(dp[i-][j]<=-)continue;
if(dp[i][j]<dp[i-][j]){
dp[i][j]=dp[i-][j];//不选
p[i][j]=j;
}
if(dp[i][j+a[i]]<dp[i-][j]+)//放在上面
{
dp[i][j+a[i]]=dp[i-][j]+;
p[i][j+a[i]]=j;
}
if(dp[i][j-a[i]]<dp[i-][j]+)//放在下面
{
dp[i][j-a[i]]=dp[i-][j]+;
p[i][j-a[i]]=j;
}
}
le-=a[i];//扩展规划范围
ri+=a[i];
}
printf("%d\n",dp[n][bas]);//回答第一问：最多使用木棍数量
int tnow=bas;//最终端点位置
int tmp;
tp1=;tp2=;
for(i=n;i>=;i--){//倒着找
tmp=p[i][tnow];//上次木棍端点位置
// printf("test: %d %d\n",tmp,tnow);
if(tmp>tnow)st2[++tp2]=tmp-tnow;
if(tmp<tnow)st1[++tp1]=tnow-tmp;
tnow=tmp;//更新位置
}
int x=,y=;
while(tp2)
{
y++;
printf("%d %d\n",x,y);
x+=st2[tp2];
printf("%d %d\n",x,y);
tp2--;
}
while(tp1)
{
y++;
printf("%d %d\n",x,y);
x-=st1[tp1];
printf("%d %d\n",x,y);
tp1--;
}
}
return ;
}