{"id":138,"date":"2010-08-04T08:41:13","date_gmt":"2010-08-04T00:41:13","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=138"},"modified":"2012-03-03T08:41:34","modified_gmt":"2012-03-03T00:41:34","slug":"%e7%8a%b6%e6%80%81%e5%8e%8b%e7%bc%a9dp","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/%e7%8a%b6%e6%80%81%e5%8e%8b%e7%bc%a9dp\/","title":{"rendered":"\u72b6\u6001\u538b\u7f29DP"},"content":{"rendered":"<p>\u8fd8\u6709\u51e0\u9053\u9898\u6b63\u5728\u6574\u7406\u3002\u3002\u8fd8\u6709\u51e0\u9053\u9898\u4e0d\u4f1a\u505a\u3002\u3002<br \/>\n\u8fd9\u51e0\u4efd\u9898\u76ee\u90fd\u662f\u7c7bTSP\u95ee\u9898\u3002\u67d0\u4e00\u4e2a\u53c2\u6570\u5c0f\u3002\u53ef\u4ee5\u7528\u72b6\u6001\u538b\u7f29DP\u53ef\u4ee5\u89e3~~~<\/p>\n<pre lang=\"cpp\" file=\"HOJ_2188.cpp\">\r\n#include <iostream>\r\n#include <cstring>\r\n#include <string>\r\nusing namespace std;\r\nconst int N = 10, M = 1 << 10;\r\nint w[N][N]; int dp[M][N];\r\nstring s[N];\r\nint n, m, ans;\r\n\r\n\r\n\/\/ updata the w[a][b] with the offset o;\r\nint f(int a, int b, int o){\r\n    int res = 0, o1, o2;\r\n    if (o<0) o1 = -o, o2 = 0; else o1 = 0, o2 = o;\r\n\r\n    for (int i=o1,j=o2;i<int(s[b].size())&#038;&#038;j<int(s[a].size());i++,j++)\r\n        if (s[b][i]==s[a][j]) res++;\r\n    return res;\r\n}\r\n\r\nvoid init(){\r\n    m = 1 << n;\r\n    for (int i=0;i<n;i++)\r\n        cin >> s[i];\r\n\r\n    memset(w, 0, sizeof(w));\r\n    for (int i=0;i<n;i++)\r\n        for (int j=0;j<n;j++){\r\n            if (i==j) continue;\r\n                          \/\/#\r\n            for (int k=1-int(s[j].size());k<int(s[i].size());k++){\r\n                \/\/cout << f(i, j, k) << endl;\r\n                w[i][j] = max(w[i][j], f(i,j,k));\r\n            }\r\n        }\r\n}\r\n\r\nvoid solve(){\r\n    memset(dp, 0, sizeof(dp));\r\n\r\n    int i, j, s, p;\r\n\r\n    for (s=0;s<m;s++)\r\n        for (i=0;i<n;i++){\r\n            p = 1 << i; if ((s&#038;p)==0) continue;\r\n            for (j=0;j<n;j++){\r\n                if (i==j||(s&#038;(1<<j))==0) continue;\r\n                dp[s][i] = max(dp[s][i], dp[s-p][j] + w[j][i]);\r\n            }\r\n        }\r\n\r\n\r\n    ans = 0;\r\n    for (i=0,m--;i<n;i++)\r\n        ans = max(ans, dp[m][i]);\r\n}\r\n\r\nint main(){\r\n    cin >> n;\r\n    while (n!=0){\r\n        init(); solve();\r\n        cout << ans << endl;\r\n        cin >> n;\r\n    }\r\n}\r\n<\/pre>\n<pre lang=\"cpp\" file=\"HOJ_2665.cpp\">\r\n#include <iostream>\r\nusing namespace std;\r\nconst int N = 15, M = (1 << 15) - 1;\r\nconst int INF = 10000000;\r\nint dp[M][N], w[N][N];\r\nint n, m, k;\r\nint ans;\r\n\r\nvoid init(){\r\n    int i, j;\r\n    m = (1 << n); k--;\r\n    int a[N], b[N];\r\n\r\n    for (i=0;i<n;i++)\r\n        cin >> a[i] >> b[i];\r\n\r\n    for (i=0;i<n;i++)\r\n        for (j=0;j<n;j++){\r\n            cin >> w[i][j];\r\n            if (i==j) w[i][j] = -INF;\r\n            else  w[i][j] = b[j] - a[j] - w[i][j];\r\n        }\r\n\r\n    for (i=0;i<m;i++)\r\n        for (j=0;j<n;j++)\r\n            dp[i][j] = - INF;\r\n\r\n    ans = dp[1<<k][k] = b[k] - a[k];\r\n}\r\n\r\nvoid patch(){\r\n    for (int i=0;i<n;i++){\r\n        for (int j=0;j<n;j++)\r\n            cout << w[i][j] << \" \";\r\n        cout << endl;\r\n    }\r\n\r\n\r\n}\r\n\r\nvoid solve(){\r\n    int i, j, s, p;\r\n\r\n    for (s=0;s<m;s++)\r\n        for (i=0;i<n;i++){\r\n            p = 1 << i; if ((s&#038;p)==0) continue;\r\n            for (j=0;j<n;j++){\r\n                if (i==j||(s&#038;(1<<j))==0) continue;\r\n                dp[s][i] = max(dp[s][i], dp[s-p][j] + w[j][i]);\r\n            }\r\n            ans = max(ans, dp[s][i]);\r\n        }\r\n}\r\n\r\nint main(){\r\n    while (cin >> n >> k){\r\n        init();  solve(); \/\/ patch();\r\n        cout << ans << endl;\r\n    }\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u8fd8\u6709\u51e0\u9053\u9898\u6b63\u5728\u6574\u7406\u3002\u3002\u8fd8\u6709\u51e0\u9053\u9898\u4e0d\u4f1a\u505a\u3002\u3002 \u8fd9\u51e0\u4efd\u9898\u76ee\u90fd\u662f\u7c7bTSP\u95ee\u9898\u3002\u67d0\u4e00\u4e2a\u53c2\u6570\u5c0f\u3002\u53ef\u4ee5\u7528\u72b6\u6001\u538b\u7f29DP\u53ef\u4ee5\u89e3~~~ #include #include #include using namespace std; const int N = 10, M = 1<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-138","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-2e","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/138","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=138"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/138\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=138"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=138"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=138"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}