vijosP1037搭建双塔

vijosP1037搭建双塔

链接:https://vijos.org/p/1037

【思路】

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 ;
}
上一篇:C#字符串Split方法的误区


下一篇:VIJOS P1037搭建双塔[DP]