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;}

1楼CS_liuqing昨天 09:45

第六题的那个连连看n对样例n10n1 2 3 4 5n1 2 3 4 5n和n12 n1 2 3 4 5 6n1 2 3 4 5 6n和n14n1 2 3 4 5 6 7n1 2 3 4 5 6 7n这些哪些是“1”，哪些是“0 “啊？n对那个距离判断不准，后面wa 了多次，确定代码没其他问题果断改边界值，ac得蛋疼。