# 11405: 【原1405】畅畅的玩具

### 题目描述

author: Drei 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1405

## Sample Input

``````5
1 3 4 5 2
``````

## Sample Output

``````7
``````

## 解释

40%的数据N<=100；60%的数据N<=200;

## WashSwang's solution

``````#include <iostream>
#include <cstring>
using namespace std;
int s,n;
int t[501][4001];//前i根棒子中 可以组成的两条长度差为j的轨道中较大的那条的长度
int main() {
cin>>n;
memset(t,-1,sizeof(t));
t[0][0]=0;
for (int i=1;i<=n;++i)
{
cin>>s;
for (int j=0;j<=2000;++j){
t[i][j]=t[i-1][j];//不加这根塑料棒
if (j>=s&&t[i-1][j-s]!=-1&&t[i-1][j-s]+s>t[i][j]) t[i][j]=t[i-1][j-s]+s;//加在较长的那条上 差值变大 较长的长度变大
if (t[i-1][j+s]>t[i][j]) t[i][j]=t[i-1][j+s];//加在较短的那条上 但并未超过较长的那条 差变小 较长的长度不变
if (s>=j&&t[i-1][s-j]!=-1&&t[i-1][s-j]+j>t[i][j]) t[i][j]=t[i-1][s-j]+j;//加在较短的那条上 超过了原来较长的那条 长度变大
}
}
if (!t[n][0]) cout<<"Impossible";
else cout<<t[n][0];
return 0;
}
``````

## yyong119's solution

``````#include <cstdio>
#include <cstring>
#include <algorithm>
#define max(x, y) ((x) > (y) ? (x) : (y))
#define MAX_N 505
#define MAX_S 2010
using namespace std;
int n, sum;
int a[MAX_N];
int f[MAX_N][MAX_S];// f_ij: max height when diff is j with 1~i toothpicks
char ch = getchar(); int res = 0;
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9')
res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return res;
}
int main() {
for (register int i = 1; i <= n; ++i) a[i] = read();
for (register int i = 1; i <= n; ++i) {
sum += a[i];
memcpy(f[i], f[i - 1], sizeof(f[0]));
for (register int j = 0; j <= sum; ++j) {
// height will at least be j when the diff is j
if (f[i - 1][j] < j) continue;
// add i-th toothpick to the longer side
int diff = j + a[i];
f[i][diff] = max(f[i][diff], f[i - 1][j] + a[i]);
// ... shorter side
diff = abs(j - a[i]);
f[i][diff] = max(f[i][diff], f[i - 1][j] + a[i]);
}
}
if (f[n][0]) printf("%d\n", f[n][0] >> 1);
else printf("Impossible");
return 0;
}
``````