{"id":142,"date":"2017-03-30T18:37:27","date_gmt":"2017-03-30T10:37:27","guid":{"rendered":"http:\/\/tys.design\/?p=142"},"modified":"2017-03-30T18:37:27","modified_gmt":"2017-03-30T10:37:27","slug":"haoi2010%e8%a7%a3%e9%a2%98%e6%8a%a5%e5%91%8a","status":"publish","type":"post","link":"https:\/\/tys.fun\/?p=142","title":{"rendered":"HAOI2010\u89e3\u9898\u62a5\u544a"},"content":{"rendered":"<p><iframe loading=\"lazy\" width=\"402\" height=\"327\" src=\"https:\/\/onedrive.live.com\/embed?cid=0E27C55C5257CF47&amp;resid=E27C55C5257CF47%21802&amp;authkey=AGhjO1ULLdk6i4M&amp;em=2\" frameborder=\"0\" scrolling=\"no\"><\/iframe><br \/>\nwoc&#8230;\u8fd9Onedrive\u597d\u8fa3\u9e21\u554a\u3002\u3002\u3002\u8bbf\u95ee\u901f\u5ea6\u771f\u662f\u4e0d\u6562\u606d\u7ef4\uff0c\u5f3a\u70c8\u5efa\u8bae\u4e0b\u8f7d\u540e\u67e5\u770b\u6b64PPT\u3002<br \/>\n\u7b97\u6cd5\u4ec0\u4e48\u7684PPT\u91cc\u90fd\u6709\uff0c\u76f4\u63a5\u8d34\u4ee3\u7801\u5427\u3002<br \/>\nT1:<\/p>\n<pre class=\"lang:c++ decode:true\">#include &lt;iostream&gt;\n#include &lt;cstdio&gt;\n#include &lt;algorithm&gt;\n#include &lt;cstdlib&gt;\n#include &lt;cstring&gt;\n#define LL long long\nusing namespace std;\nint a[55], cnt[10];\nint len;\nvoid get_line(int *t) {\n\tchar tmp = getchar();\n\twhile (tmp &lt; '0' || tmp &gt; '9') tmp = getchar();\n\twhile (tmp &lt;= '9' &amp;&amp; tmp &gt;= '0') {\n\t\tt[++len] = tmp - '0';\n\t\tcnt[t[len]]++;\n\t\ttmp = getchar();\n\t}\n}\nLL calc() {\n\tLL ans = 1;\n\tint num = 0;\n\tfor (int i = 0; i &lt;= 9; i++) {\n\t\tfor (int j = 1; j &lt;= cnt[i]; j++) {\n\t\t\tans *= (++num);\n\t\t\tans \/= j;\n\t\t}\n\t}\n\treturn ans;\n}\nint main() {\n#ifndef LOCAL\n\tfreopen(\"perm.in\", \"r\", stdin);\n\tfreopen(\"perm.out\", \"w\", stdout);\n#endif\n\tget_line(a);\n\tint num;\n\tLL ans = 0;\n\tfor (int i = 1; i &lt;= len; i++) {\n\t\tnum = a[i];\n\t\tfor (int j = 0; j &lt; num; j++) {\n\t\t\tif (!cnt[j]) continue;\n\t\t\tcnt[j]--;\n\t\t\tans += calc();\n\t\t\tcnt[j]++;\n\t\t}\n\t\tcnt[num]--;\n\t}\n\tprintf(\"%lld\\n\", ans);\n\treturn 0;\n}\n<\/pre>\n<p>T2:<\/p>\n<pre class=\"lang:c++ decode:true \">#include &lt;iostream&gt;\n#include &lt;cstdio&gt;\n#include &lt;algorithm&gt;\n#include &lt;cstring&gt;\n#define LL long long\nusing namespace std;\nconst int MX = 50005;\nint m, b, h, n;\nint a[MX], hi[MX], cost[MX];\nint sum, tot;\nclass node{\n  public:\n\t  int c, tar;\n}ns[MX];\ninline bool cmp(node a, node b) {\n\treturn a.c &lt; b.c;\n}\nconst inline int get_num() {\n\tint aa = 0;\n\tchar tmp = getchar();\n\twhile (tmp &lt; '0' || tmp &gt; '9') tmp = getchar();\n\twhile (tmp &lt;= '9' &amp;&amp; tmp &gt;= '0') {\n\t\taa = aa * 10 + tmp - '0';\n\t\ttmp = getchar();\n\t}\n\treturn aa;\n}\nint Main() {\n#ifndef LOCAL\n\tfreopen(\"factory1.in\", \"r\", stdin);\n\tfreopen(\"factory1.out\", \"w\", stdout);\n#endif\n\tm = get_num();\n\tb = get_num();\n\th = get_num();\n\tn = get_num();\n\tfor (int i = 1; i &lt;= m; i++) {\n\t\ta[i] = get_num();\n\t\tsum += a[i];\n\t}\n\tfor (int i = 1; i &lt;= n; i++) {\n\t\thi[i] = get_num();\n\t}\n\tfor (int i = 1; i &lt;= m; i++) {\n\t\tcost[i] = get_num();\n\t\ttot += cost[i] * a[i];\n\t}\n\tint pos;\n\tLL ans = 0x7fffffff, now, le;\n\tfor (int i = 1; i &lt;= n; i++) {\n\t\tfor (int j = 1; j &lt;= m; j++) {\n\t\t\tns[j].tar = j;\n\t\t\tns[j].c = get_num() - cost[j];\n\t\t}\n\t\tsort(ns + 1, ns + m + 1, cmp);\n\t\tnow = tot, le = sum - b;\n\t\tfor (int j = 1; j &lt;= m; j++) {\n\t\t\tif (le &gt; a[ns[j].tar]) {\n\t\t\t\tle -= a[ns[j].tar];\n\t\t\t\tnow += a[ns[j].tar] * ns[j].c;\n\t\t\t} else {\n\t\t\t\tnow += le * ns[j].c;\n\t\t\t\tbreak;\n\t\t\t}\n\t\t}\n\t\tif (now + hi[i] &lt; ans) {\n\t\t\tans = now + hi[i];\n\t\t\tpos = i;\n\t\t}\n\t}\n\tprintf(\"%d\\n%lld\\n\", pos, ans + h);\n\treturn 0;\n}\nint AA = Main();\nint main() {;}\n<\/pre>\n<p>T3:<\/p>\n<pre class=\"lang:c++ decode:true \">#include &lt;iostream&gt;\n#include &lt;cstdio&gt;\n#include &lt;algorithm&gt;\n#include &lt;cstring&gt;\nusing namespace std;\nconst int MX = 205;\nint m, n;\nint dfn[MX], low[MX];\nint v[MX], w[MX];\nint suv[MX], suw[MX];\nint in[MX];\nint f[105][505];\nclass edge{\n  public:\n\t  int to, ne;\n}e[MX], e2[MX];\nint _tot, _head[MX], tot, head[MX];\nclass stack_{\n  private:\n\t  int st[MX], tp, _in[MX];\n  public:\n\t  bool instack(int x) {\n\t\t  return _in[x];\n\t  }\n\t  void push(int x) {\n\t\t  st[++tp] = x;\n\t\t  _in[x]++;\n\t  }\n\t  void pop() {\n\t\t  _in[st[tp--]]--;\n\t  }\n\t  int top() {\n\t\t  return st[tp];\n\t  }\n}s;\nvoid addedge(int a, int b) {\n\t\/\/e[++tot].fr = a;\n\te[++tot].to = b;\n\te[tot].ne = head[a];\n\thead[a] = tot;\n}\nvoid addedge2(int a, int b) {\n\tin[b]++;\n\t\/\/e2[++tot].fr = a;\n\te2[++tot].to = b;\n\te2[tot].ne = _head[a];\n\t_head[a] = tot;\n}\nint belong[MX];\nint cnt, kcnt;\nvoid tarjan(int x) {\n\tint now = 0;\n\tdfn[x] = low[x] = ++cnt;\n\ts.push(x);\n\tfor (int i = head[x]; i; i = e[i].ne) {\n\t\tif (!dfn[e[i].to]) {\n\t\t\ttarjan(e[i].to);\n\t\t\tlow[x] = min(low[x], low[e[i].to]);\n\t\t} else if (s.instack(e[i].to)) {\n\t\t\tlow[x] = min(low[x], dfn[e[i].to]);\n\t\t}\n\t}\n\tif (low[x] == dfn[x]) {\n\t\tkcnt++;\n\t\twhile (now != x) {\n\t\t\tnow = s.top();\n\t\t\ts.pop();\n\t\t\tbelong[now] = kcnt;\n\t\t\tsuv[kcnt] += v[now];\n\t\t\tsuw[kcnt] += w[now];\n\t\t}\n\t}\n}\nvoid rebuild() {\n\ttot = 0;\n\tfor (int i = 1; i &lt;= n; i++) {\n\t\tfor (int j = head[i]; j; j = e[j].ne) {\n\t\t\tif (belong[e[j].to] != belong[i]) {\n\t\t\t\taddedge2(belong[i], belong[e[j].to]);\n\t\t\t}\n\t\t}\n\t}\n}\nvoid dp(int x) {\n\tfor (int i = _head[x]; i; i = e2[i].ne) {\n\t\tdp(e2[i].to);\n\t\tfor (int j = m - suw[x]; j &gt;= 0; j--) {\n\t\t\tfor (int k = 0; k &lt;= j; k++) {\n\t\t\t\tf[x][j] = max(f[x][j], f[x][k] + f[e2[i].to][j - k]);\n\t\t\t}\n\t\t}\n\t}\n\tfor (int i = m; i &gt;= 0; i--) {\n\t\tif (i &gt;= suw[x]) f[x][i] = f[x][i - suw[x]] + suv[x];\n\t\telse f[x][i] = 0;\n\t}\n}\nint main() {\n#ifndef LOCAL\n\tfreopen(\"install.in\", \"r\", stdin);\n\tfreopen(\"install.out\", \"w\", stdout);\n#endif\n\tscanf(\"%d%d\", &amp;n, &amp;m);\n\tfor (int i = 1; i &lt;= n; i++) {\n\t\tscanf(\"%d\", &amp;w[i]);\n\t}\n\tfor (int i = 1; i &lt;= n; i++) {\n\t\tscanf(\"%d\", &amp;v[i]);\n\t}\n\tint x;\n\tfor (int i = 1; i &lt;= n; i++) {\n\t\tscanf(\"%d\", &amp;x);\n\t\tif (x) {\n\t\t\taddedge(x, i);\n\t\t}\n\t}\n\tfor (int i = 1; i &lt;= n; i++) {\n\t\tif (!dfn[i]) tarjan(i);\n\t}\n\trebuild();\n\tfor (int i = 1; i &lt;= kcnt; i++) {\n\t\tif (!in[i]) {\n\t\t\taddedge2(kcnt + 1, i);\n\t\t}\n\t}\n\tdp(kcnt + 1);\n\tprintf(\"%d\\n\", f[kcnt + 1][m]);\n\treturn 0;\n}\n<\/pre>\n<p>T4:<\/p>\n<pre class=\"lang:c++ decode:true \">#include &lt;iostream&gt;\n#include &lt;cstdio&gt;\n#include &lt;algorithm&gt;\n#include &lt;cstring&gt;\n#define LL long long\nusing namespace std;\nconst int chenyao = 1e8;\nint f[5005][5005], g[5005][5005];\nchar a[5005], b[5005];\nint l1, l2;\nint get_line(char *tar) {\n\tint len = 0;\n\tchar tmp = getchar();\n\twhile (tmp &lt; 'A' || tmp &gt; 'Z') tmp = getchar();\n\twhile (tmp != '.') {\n\t\ttar[++len] = tmp;\n\t\ttmp = getchar();\n\t}\n\treturn len;\n}\nint main() {\n#ifndef LOCAL\n\tfreopen(\"lcs.in\", \"r\", stdin);\n\tfreopen(\"lcs.out\", \"w\", stdout);\n#endif\n\tl1 = get_line(a);\n\tl2 = get_line(b);\n\tfor (int i = 0; i &lt; max(l1, l2); i++) g[0][i] = g[i][0] = 1;\n\tfor (int i = 1; i &lt;= l1; i++) {\n\t\tfor (int j = 1; j &lt;= l2; j++) {\n\t\t\tif (a[i] == b[j]) {\n\t\t\t\tf[i][j] = f[i - 1][j - 1] + 1;\n\t\t\t\tg[i][j] += g[i - 1][j - 1];\n\t\t\t\tif (f[i][j - 1] == f[i][j]) g[i][j] += g[i][j - 1];\n\t\t\t\tif (f[i - 1][j] == f[i][j]) g[i][j] += g[i - 1][j];\n\t\t\t} else {\n\t\t\t\tf[i][j] = max(f[i][j - 1], f[i - 1][j]);\n\t\t\t\tif (f[i - 1][j] == f[i][j]) g[i][j] += g[i - 1][j];\n\t\t\t\tif (f[i][j - 1] == f[i][j]) g[i][j] += g[i][j - 1];\n\t\t\t\tif (f[i][j - 1] == f[i - 1][j] &amp;&amp; f[i][j] == f[i - 1][j - 1]) g[i][j] -= g[i - 1][j - 1];\n\t\t\t}\n\t\t\tg[i][j] = g[i][j] % chenyao;\n\t\t}\n\t}\n\tprintf(\"%d\\n%d\\n\", f[l1][l2], g[l1][l2]);\n}\n<\/pre>\n<p>T5:<\/p>\n<pre class=\"lang:c++ decode:true \">#include &lt;iostream&gt;\n#include &lt;cstdio&gt;\n#include &lt;algorithm&gt;\n#include &lt;cstring&gt;\nusing namespace std;\nconst int INF = 1e9 + 7;\nint n, m, s;\nint f[55][10005];\nint u[55];\nint d[55];\nint main() {\n#ifndef LOCAL\n\tfreopen(\"order.in\", \"r\", stdin);\n\tfreopen(\"order.out\", \"w\", stdout);\n#endif\n\tscanf(\"%d%d%d\", &amp;n, &amp;m, &amp;s);\n\tfor (int i = 1; i &lt;= n; i++) {\n\t\tscanf(\"%d\", &amp;u[i]);\n\t}\n\tfor (int i = 1; i &lt;= n; i++) {\n\t\tscanf(\"%d\", &amp;d[i]);\n\t}\n\tfor (int i = 1; i &lt;= s; i++) f[0][i] = INF;\n\tfor (int i = 1; i &lt;= n; i++) {\n\t\tint tmp = INF, k = 0;\n\t\tfor (int j = 0; j &lt;= s; j++) {\n\t\t\tfor (; k &lt;= min(u[i] + j, s); k++) tmp = min(tmp, f[i - 1][k] + k * (m - d[i]));\n\t\t\tf[i][j] = tmp + (u[i] + j) * d[i];\n\t\t}\n\t}\n\tprintf(\"%d\\n\", f[n][0]);\n\treturn 0;\n}\n<\/pre>\n<p>\u603b\u7ed3\u4e00\u4e0b\uff0cHAOI2010\u7684\u9898\u4e0d\u7b97\u5f88\u96be\uff0c\u4f46\u662f\u5947\u602a\u7684DP\u548c\u9700\u8981\u7528\u5230DP\u7684\u8ba1\u6570\u9898\u771f\u7684\u5f88\u70e6\u3002<br \/>\n\u8fd8\u662f\u81ea\u5df1\u592a\u5f31\uff0c\u8fde\u6700\u5c0f\u8d39\u7528\u6700\u5927\u6d41\u90fd\u4e0d\u4f1a\u5199\uff0c\u611f\u89c9\u5403\u67a3\u836f\u4e38\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>woc&#8230;\u8fd9Onedrive\u597d\u8fa3\u9e21\u554a\u3002\u3002\u3002\u8bbf\u95ee\u901f\u5ea6\u771f\u662f\u4e0d\u6562\u606d\u7ef4\uff0c\u5f3a\u70c8\u5efa\u8bae\u4e0b\u8f7d\u540e\u67e5\u770b\u6b64PPT\u3002 \u7b97\u6cd5\u4ec0 &hellip; <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[4],"tags":[],"class_list":["post-142","post","type-post","status-publish","format-standard","hentry","category-report"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/tys.fun\/index.php?rest_route=\/wp\/v2\/posts\/142","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/tys.fun\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/tys.fun\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/tys.fun\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/tys.fun\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=142"}],"version-history":[{"count":0,"href":"https:\/\/tys.fun\/index.php?rest_route=\/wp\/v2\/posts\/142\/revisions"}],"wp:attachment":[{"href":"https:\/\/tys.fun\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=142"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/tys.fun\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=142"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/tys.fun\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=142"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}