2012 ACM/ICPC Asia Regional Changchun Online 解题报告
hdu 4276 The Ghost Blows Light
这个题是树形dp比赛的时候一直超时，囧，最后将代码进行了优化，然后就过了
我的思路是，先将1到n的边先走，将走过的边时间改为0，然后其他的边都得走二次！剩下的就是简单的tree dp了，当时的代码太乱了！以至于超时！
/**1011*/#include <iostream>#include <string.h>#include <stdio.h>#include <algorithm>#include <map>#include <utility>using namespace std;int dat[100];int sum;struct note{ int a,b,c;}re[1000000];bool cmp(const note a,const note b){ return a.a < b.a || (a.a == b.a && a.b < b.b) || (a.a == b.a && a.b == b.b && a.c < b.c);}int kk;void sort(int &a,int &b,int &c){ if(a > b) swap(a,b); if(a > c) swap(a,c); if(b > c) swap(b,c);}bool check(int a,int b){ int c = sum - a - b; if(a+b > c && b + c > a && a+c > b) { //cout << a << " " << b << " " << c << "\n"; sort(a,b,c); re[kk].a = a; re[kk].b = b; re[kk].c = c; kk++; return 1; } return 0;}pair<int,int> _make_pair(int _sum,int a,int b){ int c = _sum - a - b; sort(b,a,c); if(a > b) return make_pair(a,b); return make_pair(b,a);}bool same(note a,note b){ return a.a == b.a && a.b == b.b && a.c == b.c;}int main(){ int sss = 1; for(int i = 0;i < 15;i++) sss *= 3; //cout << sss; int t,n; scanf("%d",&t); while(t--) { map < pair<int ,int > , int > dp[16]; scanf("%d",&n); for(int i = 0;i < n;i++) scanf("%d",&dat[i]); sum = 0; for(int i = 0;i < n;i++) sum += dat[i]; //pair pp(0,dat[0]); dp[0] [ make_pair(dat[0],0) ] ++; dp[0] [ make_pair(0,0) ] ++; int _sum = dat[0]; for(int i = 1;i < n;i++) { _sum += dat[i]; map<pair<int,int>,int>::iterator it = dp[i-1].begin(); for(;it!=dp[i-1].end();++it) { pair <int,int> p = it->first; dp[i][_make_pair(_sum,p.first+dat[i],p.second)]++; dp[i][_make_pair(_sum,p.first,p.second+dat[i])]++; dp[i][_make_pair(_sum,p.first,p.second)]++; } } int ree = 0; kk = 0; map<pair<int,int>,int>::iterator it = dp[n-1].begin(); for(;it!=dp[n-1].end();++it) { pair <int,int> p = it->first; check(p.first,p.second) ; } sort(re,re+kk,cmp); if(kk == 0) ree = 0; else { ree = 1; for(int i = 1;i < kk;i++) { if( !same(re[i],re[i-1]) ) ree++; } } cout << ree << "\n"; } return 0;}