vijosP1037搭建双塔
【思路】
DP。
【代码】
#include<iostream>
#include<cstring>
using namespace std; const int maxn = +; int a[maxn];
int d[maxn][];
int n,sum; int main() {
ios::sync_with_stdio(false);
cin>>n;
for(int i=;i<=n;i++) cin>>a[i] , sum+=a[i]; memset(d,-,sizeof(d));
d[][]=;
for(int i=;i<=n;i++)
for(int j=;j<=sum;j++)
{
if(d[i-][j]>-)
d[i][j]=d[i-][j];
if(a[i]>=j&&d[i-][a[i]-j]>-)
d[i][j]=max(d[i][j],d[i-][a[i]-j]+j);
if(j+a[i]<=sum&&d[i-][j+a[i]]>-)
d[i][j]=max(d[i][j],d[i-][j+a[i]]);
if(j>=a[i]&&d[i-][j-a[i]]>-)
d[i][j]=max(d[i][j],d[i-][j-a[i]]+a[i]);
}
if(d[n][]<=) cout<<"Impossible";
else cout<<d[n][]; return ;
}