{"id":135,"date":"2010-08-05T08:39:41","date_gmt":"2010-08-05T00:39:41","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=135"},"modified":"2012-03-03T08:39:59","modified_gmt":"2012-03-03T00:39:59","slug":"%e4%be%9b%e5%a5%89-88888888%e5%a7%90%e7%9a%84%e8%83%8c%e5%8c%85%e4%bb%a3%e7%a0%81","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/%e4%be%9b%e5%a5%89-88888888%e5%a7%90%e7%9a%84%e8%83%8c%e5%8c%85%e4%bb%a3%e7%a0%81\/","title":{"rendered":".[\u4f9b\u5949]..88888888\u59d0\u7684\u80cc\u5305\u4ee3\u7801&#8230;."},"content":{"rendered":"<p>\u54b3\u54b3\u3002\u3002\u6628\u5929\u524d\u5929\u7ea0\u7ed3\u4e86\u5341\u51e0\u4e2a\u5c0f\u65f6\u7684\u96be\u9898\u3002\u3002\u3002\u3002\u6211\u4f30\u8ba1\u6b64\u9898\u6211\u77ed\u65f6\u95f4\u7c7b\u8fd8\u4e0d\u80fd\u505a\u5230\u4e0dTLE\u3002\u3002\u3002<br \/>\n\u7279\u5bfb\u89c5\u6b64\u4f5c\u54c1\u7814\u8bfb\u7528\u3002\u3002<br \/>\n<!--more--><br \/>\n\u6211\u7b80\u5355\u53d9\u8ff0\u4e00\u4e0b\u9898\u610f\uff0c0\/1\u80cc\u5305\u57fa\u7840\u4e0a\uff0c\u6bcf\u4e2a\u7269\u54c1\u5c5e\u4e8e\u4e00\u96c6\u5408\uff0c\u8981\u6c42\u4e0d\u540c\u96c6\u5408\u4e2d\u7684\u7269\u54c1\u81f3\u5c11\u88ab\u9009\u4e2d\u4e00\u6b21\u3002\u3002\u3002<br \/>\n\u9898\u76ee\u5728\u8fd9\u8fb9 <a href=\"http:\/\/acm.hit.edu.cn\/judge\/show.php?Proid=2839&#038;Contestid=0\"> HOJ 2839. I love sneakers! &#8230; \u3002<\/a><\/p>\n<pre lang=\"cpp\" file=\"Snearkers.cpp\">\r\n#include <iostream>\r\n \r\nusing namespace std;\r\n \r\nstruct point{\r\n    int tp,pri,val;\r\n}a[150];\r\nint n,m,k,dp[15][21000];\r\nbool cmp(point p1, point p2){\r\n    return(p1.tp-p2.tp<0);\r\n}\r\nint main()\r\n{\r\n    int i,kk,tmp,pre,tot;\r\n    while(scanf(\"%d %d %d\",&#038;n,&#038;m,&#038;k)==3){\r\n         for(i=1;i<=n;i++)\r\n           {\r\n             scanf(\"%d %d %d\",&#038;a[i].tp,&#038;a[i].pri,&#038;a[i].val);\r\n           }\r\n         memset(dp,0,sizeof(dp));\r\n         sort(a+1,a+n+1,cmp);\r\n         a[0].tp=0; tot=0;\r\n            for(kk=1;kk<=n;kk++){\r\n              if(a[kk].tp!=a[kk-1].tp)\r\n              {\r\n                  tot++;\r\n                  for(i=0;i<=m;i++) dp[tot][i]=-1;\r\n              }\r\n              for(i=m;i>=0;i--)\r\n                if((i>=a[kk].pri))\r\n                {\r\n                    if(dp[tot][i-a[kk].pri]!=-1)\r\n                     dp[tot][i]=max(dp[tot][i-a[kk].pri]+a[kk].val,dp[tot][i]);\r\n                    if(dp[tot-1][i-a[kk].pri]!=-1)\r\n                    dp[tot][i]=max(dp[tot][i],dp[tot-1][i-a[kk].pri]+a[kk].val);\r\n                }else break;\r\n            }\r\n           if(dp[tot][m]!=-1&&tot==k)printf(\"%d\\n\",dp[tot][m]);\r\n           else printf(\"Impossible\\n\");\r\n \r\n \r\n    }\r\n    return 0;\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u54b3\u54b3\u3002\u3002\u6628\u5929\u524d\u5929\u7ea0\u7ed3\u4e86\u5341\u51e0\u4e2a\u5c0f\u65f6\u7684\u96be\u9898\u3002\u3002\u3002\u3002\u6211\u4f30\u8ba1\u6b64\u9898\u6211\u77ed\u65f6\u95f4\u7c7b\u8fd8\u4e0d\u80fd\u505a\u5230\u4e0dTLE\u3002\u3002\u3002 \u7279\u5bfb\u89c5\u6b64\u4f5c\u54c1\u7814\u8bfb\u7528\u3002\u3002<\/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-135","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-2b","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/135","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=135"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/135\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=135"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=135"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=135"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}