{"id":558,"date":"2019-01-06T21:27:47","date_gmt":"2019-01-06T13:27:47","guid":{"rendered":"http:\/\/SmokeyDays.top\/wordpress\/?p=558"},"modified":"2019-01-06T21:27:47","modified_gmt":"2019-01-06T13:27:47","slug":"lp2766-%e7%bd%91%e7%bb%9c%e6%b5%8124%e9%a2%98-%e6%9c%80%e9%95%bf%e4%b8%8d%e4%b8%8b%e9%99%8d%e5%ad%90%e5%ba%8f%e5%88%97%e9%97%ae%e9%a2%98","status":"publish","type":"post","link":"http:\/\/SmokeyDays.top\/wordpress\/2019\/01\/06\/lp2766-%e7%bd%91%e7%bb%9c%e6%b5%8124%e9%a2%98-%e6%9c%80%e9%95%bf%e4%b8%8d%e4%b8%8b%e9%99%8d%e5%ad%90%e5%ba%8f%e5%88%97%e9%97%ae%e9%a2%98\/","title":{"rendered":"lp2766 \u7f51\u7edc\u6d4124\u9898-\u6700\u957f\u4e0d\u4e0b\u964d\u5b50\u5e8f\u5217\u95ee\u9898"},"content":{"rendered":"\n

\u8fd9\u662f\u4e00\u9053\u770b\u8d77\u6765\u5f88\u7b80\u5355\u7684\u9ebb\u9898\u3002
\n\u5f88\u663e\u7136\u53ef\u4ee5\u53d1\u73b0\u7b2c\u4e00\u95ee\u5c31\u662f\u76f4\u63a5n^2DP\u6c42\u4e00\u4e2a\u7b54\u6848\u3002
\n\u7b2c\u4e8c\u95ee\u6a21\u62df\u5bfb\u627e\u6700\u957f\u4e0d\u4e0b\u964d\u5b50\u5e8f\u5217\u7684\u8fc7\u7a0b\u3002
\n\u7b2c\u4e09\u95ee\u6539\u51e0\u6761\u8fb9\u518d\u8dd1\u4e00\u904d\u3002
\n\u4f46\u662f\u8981\u6ce8\u610f\u5f88\u591a\u5f88\u591a\u7ec6\u8282\u3002
\n\u6bd4\u5982\u8bf4\uff0c\u5efa\u6a21\u7684\u65f6\u5019\u5e94\u8be5\u53cd\u7740\u5efa\u3002
\n\u518d\u6bd4\u5982\u8bf4\uff0c\u5bf9\u4e8e\u6700\u957f\u957f\u5ea6\u53ea\u67091\u7684\u60c5\u51b5\u5e94\u5f53\u683c\u5916\u6ce8\u610f\uff0c\u56e0\u4e3a\u8fd9\u53ef\u80fd\u4f1a\u5bfc\u81f4\u5404\u79cd\u9519\u8bef\u3002
\n\u5199\u8d77\u6765\u8fd8\u662f\u6709\u70b9\u70e6\u5fc3\u7684\u3002 <\/p>\n\n\n\n

#include<iostream>\n#include<cstdio>\n#include<cstring>\n#include<algorithm>\n#include<queue>\n#include<vector>\n\nconst int INF=0x3f3f3f3f;\nconst int BIG=19260817;\ninline int Min(int A,int B){\n\treturn A<B?A:B;\n}\n\ninline int Max(int A,int B){\n\treturn A>B?A:B;\n}\n\nstruct ee{\n\tint v;\n\tint w;\n\tint nxt;\n}e[250005];\nint h[2005],et=-1;\n\ninline void Eadd(int U,int V,int W){\n\te[++et]=(ee){V,W,h[U]};\n\th[U]=et; \n}\ninline void add(int U,int V,int W){\n\tEadd(U,V,W);\n\tEadd(V,U,0);\n}\n\nint dep[2005],nw[2005],a[505];\nint n,s,t,len;\nstd::queue<int> q;\ninline bool bfs(){\n\tfor(int i=1;i<=t;++i){\n\t\tdep[i]=INF,nw[i]=h[i];\n\t}\n\tdep[s]=1;\n\twhile(!q.empty()){\n\t\tq.pop();\n\t}\n\tq.push(s);\n\tint p;\n\twhile(!q.empty()){\n\t\tp=q.front();\n\t\tq.pop();\n\t\tfor(int i=h[p];i>=0;i=e[i].nxt){\n\t\t\tif(dep[e[i].v]==INF&&e[i].w){\n\t\t\t\tdep[e[i].v]=dep[p]+1;\n\t\t\t\tq.push(e[i].v);\n\t\t\t}\n\t\t}\n\t}\n\/\/\tfor(int i=1;i<=t;++i){\n\/\/\t\tprintf(\"%d \",dep[i]);\n\/\/\t}\n\/\/\tputs(\"\");\n\treturn dep[t]^INF;\n}\n\ninline int dfs(int X,int V){\n\tif(!V||X==t){\n\t\treturn V;\n\t}\n\tint cnt=0,val;\n\tfor(int i=nw[X];i>=0;i=e[i].nxt){\n\t\tnw[X]=i;\n\t\tif(dep[e[i].v]==dep[X]+1){\n\t\t\tval=dfs(e[i].v,Min(V,e[i].w));\n\t\t\tif(val){\n\t\t\t\tcnt+=val;\n\t\t\t\tV-=val;\n\t\t\t\te[i].w-=val;\n\t\t\t\te[i^1].w+=val;\n\t\t\t\tif(!V){\n\t\t\t\t\tbreak;\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\treturn cnt;\n}\nint f[505];\ninline void slv1(){\n\tfor(int i=1;i<=n;++i){\n\t\tf[i]=1;\n\t\tfor(int j=1;j<i;++j){\n\t\t\tif(a[i]>=a[j]){\n\t\t\t\tf[i]=Max(f[i],f[j]+1);\n\t\t\t}\n\t\t}\n\t}\n\tint ans=0;\n\tfor(int i=1;i<=n;++i){\n\t\tans=Max(ans,f[i]);\n\t}\n\tlen=ans;\n\tprintf(\"%d\\n\",ans);\n}\n\ninline int dinic(){\n\tint RT=0;\n\twhile(bfs()){\n\t\tRT+=dfs(s,INF);\n\t}\n\treturn RT;\n}\n\ninline void slv2(){\n\ts=2*n+1,t=2*n+2;\n\tfor(int i=1;i<=t;++i){\n\t\th[i]=-1;\n\t}\n\tet=-1;\n\tfor(int i=1;i<=n;++i){\n\t\tif(f[i]==len){\n\t\t\tadd(i+n,t,1);\n\t\t}\n\t\tif(f[i]==1){\n\t\t\tadd(s,i,1);\n\t\t}\n\t\tadd(i,i+n,1);\n\t\tfor(int j=1;j<i;++j){\n\t\t\tif(a[i]>=a[j]&&f[j]+1==f[i]){\n\t\t\t\tadd(j+n,i,1);\n\t\t\t}\n\t\t}\n\t}\n\tint ans=0;\n\twhile(bfs()){\n\t\tans+=dfs(s,INF);\n\t}\n\tprintf(\"%d\\n\",ans);\n\tadd(1,n+1,BIG),add(s,1,BIG);\n\tif(f[n]==len){\n\t\tadd(n,2*n,BIG),add(2*n,t,BIG);\n\t}\n\twhile(bfs()){\n\t\tans+=dfs(s,INF);\n\t}\n\tprintf(\"%d\\n\",ans);\n}\n\nvoid init(){\n\tscanf(\"%d\",&n);\n\tfor(int i=1;i<=n;++i){\n\t\tscanf(\"%d\",a+i);\n\t}\n\tslv1();\n\tslv2();\n}\nint main(){\n\tinit();\n\treturn 0;\n}\n\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u8fd9\u662f\u4e00\u9053\u770b\u8d77\u6765\u5f88\u7b80\u5355\u7684\u9ebb\u9898\u3002 \u5f88\u663e\u7136\u53ef\u4ee5\u53d1\u73b0\u7b2c\u4e00\u95ee\u5c31\u662f\u76f4\u63a5n^2DP\u6c42\u4e00\u4e2a\u7b54\u6848\u3002 \u7b2c\u4e8c\u95ee\u6a21\u62df\u5bfb\u627e\u6700\u957f\u4e0d\u4e0b\u964d\u5b50\u5e8f … <\/p>\n
\u7ee7\u7eed\u9605\u8bfb\u201clp2766 \u7f51\u7edc\u6d4124\u9898-\u6700\u957f\u4e0d\u4e0b\u964d\u5b50\u5e8f\u5217\u95ee\u9898\u201d<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[76,8,6,75,78,5],"tags":[],"_links":{"self":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/558"}],"collection":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/comments?post=558"}],"version-history":[{"count":1,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/558\/revisions"}],"predecessor-version":[{"id":559,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/558\/revisions\/559"}],"wp:attachment":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/media?parent=558"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/categories?post=558"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/tags?post=558"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}