Description
Input
Output
Sample Input
1 10 20 30 2 6 8 10 5 5 5 7 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 5 31 41 59 26 53 58 97 93 23 84 62 64 33 83 27 0
Sample Output
Case 1: maximum height = 40 Case 2: maximum height = 21 Case 3: maximum height = 28 Case 4: maximum height = 342
Hint
n<=30。
Solution
一眼看出这是个DAG上的DP，一个信息分成三个方块存储。然后开始读入，拓扑，输出，过样例，提交，WA……
这里的关键是拓扑序应该怎么求。首先我的比较函数写法如下：
inline bool cmp(const Block &a,const Block &b) { return (a.l1<b.l1&&a.l2<b.l2)||(a.l2<b.l1&&a.l1<b.l2); }
然后由于sort的一些问题，这么写会挂掉。hack数据：我丢了……
然后就来想想这个拓扑怎么求。
考虑二元组(a,b)表示方块的长和宽，由于长和宽的顺序对放置无影响，所以不妨设a>=b。
引理：若1能放在2上面，则2不能放在1上面。
证明： 由题设，a1>a2，b1>b2。
当2能放在1上面，a2>a1，b2>b1。矛盾。引理得证。
定理：若a1+b1=a2+b2，则这两个方块不能叠放。
证明：不妨设a1>=a2。当a1==a2时，b1==b2。又a>b。显然不成立
当a1>a2，则b1<b2。故不成立。
定理：当且仅当a1+b1<a2+b2时，方块2可能叠放在1上面。
证明：已证相等时不成立，现在证明前者大于后者时不成立。
前者大于后者时，a1+b1>a2+b2。
当a1<a2，显然b1>b2。不成立。
当a1>a2，b1>b2，由引理，不成立。
当a1>a2，b1<b2，显然不成立。
下面证明可能性
当a1<a2，b1<b2时，满足原式，可以叠放。
定理得证。
由上述定理知，设si=ai+bi，则f[i]只可能由{f[j]|sj<si}转移得到。故将a+b得值设为阶段，进行转移。
Code
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #define maxn 100 inline void qr(int &x) { char ch=getchar();int f=1; while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); x*=f; return; } inline int max(const int &a,const int &b) {if(a>b) return a;else return b;} inline int min(const int &a,const int &b) {if(a<b) return a;else return b;} inline int abs(const int &x) {if(x>0) return x;else return -x;} inline void swap(int &a,int &b) { int c=a;a=b;b=c;return; } int n,a,b,c,frog[maxn]; struct Block { int h,l1,l2; }; Block block[maxn];int top,cnt,ans; inline void add(int x,int y,int z) { block[++top].h=x;block[top].l1=y;block[top].l2=z; if(block[top].l1<block[top].l2) swap(block[top].l2,block[top].l1); block[++top].h=y;block[top].l1=x;block[top].l2=z; if(block[top].l1<block[top].l2) swap(block[top].l2,block[top].l1); block[++top].h=z;block[top].l1=x;block[top].l2=y; if(block[top].l1<block[top].l2) swap(block[top].l2,block[top].l1); } void clear() { std::memset(block,0,sizeof block);top=0; std::memset(frog,0,sizeof frog);ans=0; } inline bool cmp(const Block &a,const Block &b) { int sa=a.l1+a.l2,sb=b.l1+b.l2; return sa<sb; } inline bool judge(const Block &a,const Block &b) { return (a.l1<b.l1&&a.l2<b.l2)||(a.l2<b.l1&&a.l1<b.l2); } int main() { qr(n); while(n) { clear(); for(int i=1;i<=n;++i) { a=b=c=0;qr(a);qr(b);qr(c); add(a,b,c); } std::sort(block+1,block+1+top,cmp); for(int i=1;i<=top;++i) { int &emm=block[i].h; frog[i]=emm; for(int j=1;j<i;++j) { if(judge(block[j],block[i])) frog[i]=max(frog[i],frog[j]+emm); } ans=max(ans,frog[i]); } printf("Case %d: maximum height = %d ",++cnt,ans); n=0;qr(n); } return 0; }
Summary
1、写完dp和爆搜对拍一下！！！
2、dp中阶段可能是一个非常难以想象的量，比如二元组的求和，在求拓扑序时可以考虑一些特殊性质。
3、求拓扑序慎用sort