Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"panda_2134","updateTime":1499326053000,"title":"求教 HDU-1011","dislikeCnt":0,"content":"[problem:HDU-1011] Submission:[submission:9485154]\n不是很懂为何TLE\n房间里面bug数量为0的特殊情况考虑到了,能优化的都优化了\n和标程也对拍了一个小时了\n\u003d \u003d\n\n\n-----\nCode:\n```\n#include\u003ccstdio\u003e\n#include\u003ccstdlib\u003e\n#include\u003ciostream\u003e\n#include\u003ccstring\u003e\n#include\u003calgorithm\u003e\n#include\u003ccctype\u003e\n#define CLEAR(x) memset(x,0,sizeof(x))\n#define SETNINF(x) memset(x,0xCF,sizeof(x))\n#define SETINF(x) memset(x,0x3F,sizeof(x))\n#define INF 0x3F3F3F3F\nusing namespace std;\ntypedef long long LL;\nstruct Edge{\n\tint v,next;\n};\nconst static int MAXN\u003d110,MAXM\u003d210;\nint e\u003d1;\nint head[MAXN];\nEdge a[MAXM];\nvoid addedge(int u,int v){\n\ta[e]\u003d(Edge){v,head[u]};head[u]\u003de++;\n}\nint n,m;bool vis[210];\nint c[110],w[110];\nLL opt[210][210];\ninline int readint(){\n\tint f\u003d1,r\u003d0;char c\u003dgetchar();\n\twhile(!isdigit(c)){if(c\u003d\u003d\u0027-\u0027)f\u003d-1;c\u003dgetchar();}\n\twhile(isdigit(c)){r\u003dr*10+c-\u00270\u0027;c\u003dgetchar();}\n\treturn f*r;\n}\ninline int cal(int x){\n\treturn x/20+(bool)(x%20);\n}\nbool init(){\n\tn\u003dreadint();m\u003dreadint(); \n\tif(n\u003d\u003d-1) return false;\n\tfor(int i\u003d1;i\u003c\u003dn;i++){\n\t\tc[i]\u003dcal(readint());w[i]\u003dreadint();\n\t} \n\tfor(int i\u003d1;i\u003c\u003dn-1;i++){\n\t\tint a,b;a\u003dreadint();b\u003dreadint();\n\t\taddedge(a,b);\n\t\taddedge(b,a);\n\t}\n\tSETNINF(opt);\n\treturn true;\n}\nvoid dp(int u){\n\tif(!c[u]){\n\t\topt[u][0]\u003dw[u];\n\t\tfor(int ii\u003dhead[u];ii;ii\u003da[ii].next){\n\t\t\tvis[u]\u003dtrue;\n\t\t\tint v\u003da[ii].v;\n\t\t\tif(vis[v])continue;else dp(v);\n\t\t\tfor(int i\u003dm;i\u003e\u003d1;i--)\n\t\t\t\tfor(int j\u003d1;j\u003c\u003di;j++)\n\t\t\t\t\topt[u][i]\u003dmax(opt[u][i],opt[u][i-j]+opt[v][j]);\n\t\t}\n\t\topt[u][0]\u003d0;\n\t\topt[u][1]\u003dmax(opt[u][1],(LL)w[u]);\n\t}else{\n\t\topt[u][0]\u003d0;\n\t\topt[u][c[u]]\u003d(LL)w[u];\n\t\tfor(int ii\u003dhead[u];ii;ii\u003da[ii].next){\n\t\t\tvis[u]\u003dtrue;\n\t\t\tint v\u003da[ii].v;\n\t\t\tif(vis[v])continue;else dp(v);\n\t\t\tfor(int i\u003dm;i\u003e\u003dc[u];i--)\n\t\t\t\tfor(int j\u003d1;j\u003c\u003di-c[u];j++)\n\t\t\t\t\topt[u][i]\u003dmax(opt[u][i],opt[u][i-j]+opt[v][j]);\n\t\t}\t\n\t}\n}\nvoid clear(){\n\te\u003d1;CLEAR(head);CLEAR(a);\n\tCLEAR(c); CLEAR(w); CLEAR(vis); SETNINF(opt); \n}\nint main(){\n\tfreopen(\"in.txt\",\"r\",stdin);\n\tfreopen(\"o1.txt\",\"w\",stdout);\n\twhile(init()){\n\t\tif(!m){printf(\"0\\n\");continue;}\n\t\tdp(1);LL ans\u003d0;\n\t\tfor(int i\u003d1;i\u003c\u003dm;i++)\n\t\t\tans\u003dmax(ans,opt[1][i]);\n\t\tprintf(\"%lld\\n\",ans);\n\t\tclear(); \n\t}\n\n\treturn 0;\n}\n```","threadId":15245,"likeCnt":0,"createTime":1499325967000,"isWorkbook":false,"viewCnt":2707,"openness":2,"fav":false,"id":154,"trustable":false}