前言：
我好像离上次写blog有1个月了吧，想想现在太浪了，写篇题解压压惊Σ( ° △ °|||)︴。
描述
2001年9月11日，一场突发的灾难将纽约世界贸易中心大厦夷为平地，Mr. F曾亲眼目睹了这次灾难。为了纪念“9?11”事件，Mr. F决定自己用水晶来搭建一座双塔。
Mr. F有N块水晶，每块水晶有一个高度，他想用这N块水晶搭建两座有同样高度的塔，使他们成为一座双塔，Mr. F可以从这N块水晶中任取M（1≤M≤N）块来搭建。但是他不知道能否使两座塔有同样的高度，也不知道如果能搭建成一座双塔，这座双塔的最大高度是多少。所以他来请你帮忙。
给定水晶的数量N（1≤N≤100）和每块水晶的高度Hi（N块水晶高度的总和不超过2000），你的任务是判断Mr. F能否用这些水晶搭建成一座双塔（两座塔有同样的高度），如果能，则输出所能搭建的双塔的最大高度，否则输出“Impossible”。
格式
输入格式
输入的第一行为一个数N，表示水晶的数量。第二行为N个数，第i个数表示第i个水晶的高度。
输出格式
输出仅包含一行，如果能搭成一座双塔，则输出双塔的最大高度，否则输出一个字符串“Impossible”。
样例1
样例输入1
5
1 3 4 5 2样例输出1
7来源
某校NOIP模拟题
这题非常有意思，
大暴力肯定是不行的，这里有明显的重叠子问题，我们可以试试看动态规划，
首先，我们确定一下它的最优子结构，
f[i][j][k]表示前i个积木是否能有一塔为j,另一塔为k的情况。
转移非常好写（这里就不写了），并且我们可以用背包的思想干掉一维，
代码：
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstring> 5 #include<cmath> 6 #include<cstdlib> 7 #include<vector> 8 using namespace std; 9 typedef long long ll; 10 typedef long double ld; 11 typedef pair<int,int> pr; 12 const double pi=acos(-1); 13 #define rep(i,a,n) for(int i=a;i<=n;i++) 14 #define per(i,n,a) for(int i=n;i>=a;i--) 15 #define Rep(i,u) for(int i=head[u];i;i=Next[i]) 16 #define clr(a) memset(a,0,sizeof(a)) 17 #define pb push_back 18 #define mp make_pair 19 #define fi first 20 #define sc second 21 #define pq priority_queue 22 #define pqb priority_queue <int, vector<int>, less<int> > 23 #define pqs priority_queue <int, vector<int>, greater<int> > 24 #define vec vector 25 ld eps=1e-9; 26 ll pp=1000000007; 27 ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;} 28 ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;} 29 void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); } 30 //void add(int x,int y,int z){ v[++e]=y; next[e]=head[x]; head[x]=e; cost[e]=z; } 31 int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1}; 32 ll read(){ ll ans=0; char last=' ',ch=getchar(); 33 while(ch<'0' || ch>'9')last=ch,ch=getchar(); 34 while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar(); 35 if(last=='-')ans=-ans; return ans; 36 } 37 const int N=2005; 38 int f[N][N],a[N],sum; 39 int main() 40 { 41 int n=read(); 42 for (int i=1;i<=n;i++) a[i]=read(),sum+=a[i]; f[0][0]=1; 43 for (int k=1;k<=n;k++) 44 for (int i=sum;i>=0;i--) 45 for (int j=sum;j>=0;j--){ 46 f[i][j]=((i-a[k]>=0)?f[i-a[k]][j]:0)|((j-a[k]>=0)?f[i][j-a[k]]:0)|f[i][j]; 47 } 48 for (int i=sum;i>=1;i--) 49 if (f[i][i]) { 50 printf("%d",i); 51 return 0; 52 } 53 printf("Impossible"); 54 return 0; 55 }
时间复杂度：Sum^2*n;
肯定是过不了的，但数据水一不小心就过了（雾）。
想到这里我们有没有感觉最后一位只存0/1有点浪费。
于是乎，
f[i][j]表示前i个积木一塔为j的离他最近的塔的高度。
可是很气的是这不是一个最优子结构，（反例自己找），
陷入了沉思，
用一塔的高度做状态不行，那差呢》》？
f[i][j]表示前i个积木差为i的最矮的塔高。
试试看转移：
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstring> 5 #include<cmath> 6 #include<cstdlib> 7 #include<vector> 8 using namespace std; 9 typedef long long ll; 10 typedef long double ld; 11 typedef pair<int,int> pr; 12 const double pi=acos(-1); 13 #define rep(i,a,n) for(int i=a;i<=n;i++) 14 #define per(i,n,a) for(int i=n;i>=a;i--) 15 #define Rep(i,u) for(int i=head[u];i;i=Next[i]) 16 #define clr(a) memset(a,0,sizeof(a)) 17 #define pb push_back 18 #define mp make_pair 19 #define fi first 20 #define sc second 21 #define pq priority_queue 22 #define pqb priority_queue <int, vector<int>, less<int> > 23 #define pqs priority_queue <int, vector<int>, greater<int> > 24 #define vec vector 25 ld eps=1e-9; 26 ll pp=1000000007; 27 ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;} 28 ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;} 29 void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); } 30 //void add(int x,int y,int z){ v[++e]=y; next[e]=head[x]; head[x]=e; cost[e]=z; } 31 int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1}; 32 ll read(){ ll ans=0; char last=' ',ch=getchar(); 33 while(ch<'0' || ch>'9')last=ch,ch=getchar(); 34 while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar(); 35 if(last=='-')ans=-ans; return ans; 36 } 37 int n,a[101],f[101][2001],h; 38 int main() 39 { 40 n=read(); 41 for (int i=1;i<=n;i++) a[i]=read(),h+=a[i]; 42 for (int i=0;i<=n;i++) 43 for (int j=0;j<=h;j++) 44 f[i][j]=-50000; 45 f[0][0]=0; 46 for (int i=1;i<=n;i++) 47 for (int j=h;j>=0;j--) 48 { 49 f[i][j]=max(f[i][j],f[i-1][j]); 50 f[i][j]=max(f[i][j],f[i-1][j+a[i]]+a[i]); 51 if (j>=a[i]) 52 f[i][j]=max(f[i][j],f[i-1][j-a[i]]); 53 else 54 f[i][j]=max(f[i][j],f[i-1][a[i]-j]+a[i]-j); 55 } 56 if (f[n][0]<=0) 57 printf("%s","Impossible"); 58 else 59 printf("%d ",f[n][0]); 60 }
终于这道题完美的解决了。