{"id":331,"date":"2020-04-19T15:34:57","date_gmt":"2020-04-19T07:34:57","guid":{"rendered":"http:\/\/www.zyhcoding.club\/?p=331"},"modified":"2020-04-19T17:55:17","modified_gmt":"2020-04-19T09:55:17","slug":"4-16%e8%a1%a5%e9%a2%98-%e7%ac%ac3%e6%ac%a1%e8%ae%ad%e7%bb%83","status":"publish","type":"post","link":"http:\/\/www.zyhcoding.club\/index.php\/2020\/04\/19\/4-16%e8%a1%a5%e9%a2%98-%e7%ac%ac3%e6%ac%a1%e8%ae%ad%e7%bb%83\/","title":{"rendered":"4-16\u8865\u9898 \u7b2c3\u6b21\u8bad\u7ec3"},"content":{"rendered":"

F Space Elevator <\/a><\/h3>\n

\u725b\u60f3\u4e0a\u592a\u7a7a\uff0c\u6ca1\u8bdd\u8bf4\u3002\u7528k\u79cd\u79ef\u6728\u6765\u642d\u5efa\u4e00\u4e2a\u68af\u5b50\u3002\u6bcf\u79cd\u79ef\u6728\u90fd\u6709\u4e09\u4e2a\u53c2\u6570\uff1a\u6570\u91cfc\uff0c\u9ad8\u5ea6h\uff0c\u8fd9\u79cd\u79ef\u6728\u6700\u5927\u80fd\u5230\u8fbe\u7684\u9ad8\u5ea6a\uff0c\u5373\u8fd9\u79cd\u79ef\u6728\u4e0d\u80fd\u642d\u5728a\u4ee5\u4e0a\u7684\u5730\u65b9\u3002
\n\u6570\u636e\u91cf\u8f83\u5c0f\uff0c01\u80cc\u5305\u548c\u591a\u91cd\u80cc\u5305\u90fd\u53ef\uff0c\u5148\u628a\u8fd9\u4e9b\u79ef\u6728\u6309\u7167\u6700\u5927\u9ad8\u5ea6a\u4ece\u5c0f\u5230\u5927\u6392\u5e8f\uff0c\u7136\u540e\u518d\u6c42\u89e3\u95ee\u9898\u3002
\n\u8fd8\u8981\u6ce8\u610f\u4e00\u70b9\uff0c\u518d\u6700\u7ec8\u8f93\u51fa\u7b54\u6848\u65f6\uff0c\u56e0\u4e3a\u6240\u6709\u79ef\u6728\u7684a\u4e0d\u540c\uff0c\u7b54\u6848\u53ef\u80fd\u4e0d\u5728dp[max_a]\u91cc\uff0c\u8981\u904d\u5386\u4e00\u6b21dp\u5bfb\u627e\u7b54\u6848\u3002dp[i]\u8868\u793a\u9ad8\u5ea6\u5c0f\u4e8ei\u65f6\u68af\u5b50\u7684\u6700\u5927\u9ad8\u5ea6\u3002<\/p>\n

#include <algorithm>\n#include <cstdio>\n#include <cstring>\n#include <vector>\nusing namespace std;\ntypedef struct block{\n    int h,a;\n}block;\nblock tmp;\nvector<block> v;\nint dp[40500];\nbool cmp(block a,block b){\n    return a.a < b.a;\n}\nint main(){\n    int k,tot=0;\n    int a,c,h;\n    scanf ("%d",&k);\n    v.reserve(4000);\n    for (int i=1;i<=k;i++){\n        scanf ("%d %d %d",&h,&tmp.a,&c);\n        int j=1;\n        for (j=1;2*j-1<=c;j<<=1){\n            tmp.h = h*j;\n            v.push_back(tmp);\n        }\n        if (j-1<c){\n            tmp.h = h * (c-j+1);\n            v.push_back(tmp);\n        }\n    }\n    sort(v.begin(),v.end(),cmp);\n    tot = v.size();\n    for (int i=0;i<tot;i++){\n        for (int j=v[i].a;j>=v[i].h;j--){\n            dp[j] = max(dp[j],dp[j-v[i].h]+v[i].h);\n        }\n    }\n    int ans = 0;\n    for (int i=0;i<=v[tot-1].a;i++) ans = max(ans,dp[i]);\n    printf ("%d\\n",ans);\n    return 0;\n}<\/code><\/pre>\n
J Two strings<\/a><\/h3>\n
\u5b57\u7b26\u4e32\u5339\u914d+dp\uff0c\u8f93\u5165\u4e24\u4e2a\u5b57\u7b26\u4e32\u662fs1,s2\uff0c\u95ees2\u662f\u5426\u53ef\u4ee5\u5339\u914d\u51fas1.
\n'.'\u53ef\u4ee5\u5339\u914d\u4efb\u610f\u4e00\u4e2a\u5b57\u7b26\uff0c'*'\u53ef\u4ee5\u5c06\u524d\u9762\u7684\u5b57\u7b26\u590d\u5236\u4efb\u610f\u6b21\u3002
\ns1\u4e2d\u7684\u5b57\u7b26\u88ab\u5339\u914d\u7684\u60c5\u51b5\u6709\u4ee5\u4e0b\u51e0\u79cd\uff1a
\n1.\u88ab\u76f8\u540c\u7684\u5b57\u7b26\u5339\u914d
\n2.\u88ab'.'\u5339\u914d
\n3.\u88ab'*'\u590d\u5236\u5339\u914d
\n\u56e0\u4e3a\u5728leetcode\u4e2d\u78b0\u5230\u8fc7\u76f8\u4f3c\u7684\u9898\u76ee\uff0c\u5728leetcode\u4e2d<"abc","a.*">\u662f\u53ef\u4ee5\u5339\u914d\u6210\u529f\u7684\uff0c\u5728\u8fd9\u9053\u9898\u4e2d\u5374\u4e0d\u884c\uff0c\u5bfc\u81f4wa\u4e86n\u6b21\u3002\u8fd8\u8981\u6ce8\u610f\u8fd9\u9053\u9898\u4e2d*\u53ef\u80fd\u541e\u566c\u5b83\u524d\u9762\u7684\u90a3\u4e2a\u5b57\u7b26(\u590d\u52360\u6b21)\u3002<\/p>\n
#include <algorithm>\n#include <cstring>\n#include <vector>\n#include <iostream>\nusing namespace std;\nconst int maxn = 2505; \nint len1,len2;\nbool dp[maxn][maxn];\nchar s1[maxn],s2[maxn];\nint main(){\n    std::ios::sync_with_stdio(false);\n    int t;\n    cin >> t;\n    while (t--){\n        cin >> s1+1 >> s2+1;\n        memset (dp,0,sizeof dp);\n        len1 = strlen(s1+1),len2 = strlen(s2+1);\n        dp[0][0] = 1;\n        int x = 0;\n        while (s2[x+2]=='*')    dp[0][x] = 1,x += 2;\n        for (int i=1;i<=len1;i++){\n            for (int j=1;j<=len2;j++){\n                if (s1[i]==s2[j] || s2[j]=='.') dp[i][j] = dp[i-1][j-1];\n                if (s2[j]=='*'){\n                    if (dp[i][j-2] || dp[i][j-1] || (s1[i-1]==s1[i] && dp[i-1][j]))\n                        dp[i][j] = 1;\n                }\n            }\n        }\n        cout << (dp[len1][len2]?"yes":"no") << endl;\n    }\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
F Space Elevator \u725b\u60f3\u4e0a\u592a\u7a7a\uff0c\u6ca1\u8bdd\u8bf4\u3002\u7528k\u79cd\u79ef\u6728\u6765\u642d\u5efa\u4e00\u4e2a\u68af\u5b50\u3002\u6bcf\u79cd\u79ef\u6728\u90fd\u6709\u4e09\u4e2a\u53c2\u6570 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[31],"tags":[],"_links":{"self":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/331"}],"collection":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/comments?post=331"}],"version-history":[{"count":6,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/331\/revisions"}],"predecessor-version":[{"id":339,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/331\/revisions\/339"}],"wp:attachment":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/media?parent=331"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/categories?post=331"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/tags?post=331"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}