{"id":199,"date":"2010-03-29T17:59:00","date_gmt":"2010-03-29T09:59:00","guid":{"rendered":"http:\/\/localhost\/?p=199"},"modified":"2010-03-29T17:59:00","modified_gmt":"2010-03-29T09:59:00","slug":"usaco2008_oct_construction_fence","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=199","title":{"rendered":"[Usaco2008 Oct]\u5efa\u9020\u6805\u680f"},"content":{"rendered":"\n

[Usaco2008 Oct]\u5efa\u9020\u6805\u680f<\/p>\n

Time Limit:5000MS Memory Limit:65536K
Total Submit:6 Accepted:6
Case Time Limit:1000MS<\/p>\n

Description <\/strong><\/p>\n

\u52e4\u594b\u7684Farmer John\u60f3\u8981\u5efa\u9020\u4e00\u4e2a\u56db\u9762\u7684\u6805\u680f\u6765\u5173\u4f4f\u725b\u4eec\u3002\u4ed6\u6709\u4e00\u5757\u957f\u4e3an\uff084<=n<=2500\uff09\u7684\u6728\u677f\uff0c\u4ed6\u60f3\u628a\u8fd9\u5757\u672c\u677f\u5207\u62104\u5757\u3002
\u8fd9\u56db\u5757\u5c0f\u6728\u677f\u53ef\u4ee5\u662f\u4efb\u4f55\u4e00\u4e2a\u957f\u5ea6\u53ea\u8981Farmer John\u80fd\u591f\u628a\u5b83\u4eec\u56f4\u6210\u4e00\u4e2a\u5408\u7406\u7684\u56db\u8fb9\u5f62\u3002\u4ed6\u80fd\u591f\u5207\u51fa\u591a\u5c11\u79cd\u4e0d\u540c\u7684\u5408\u7406\u65b9\u6848\u3002
\u6ce8\u610f\uff1a <\/p>\n

*\u53ea\u8981\u5927\u6728\u677f\u7684\u5207\u5272\u70b9\u4e0d\u540c\u5c31\u5f53\u6210\u662f\u4e0d\u540c\u7684\u65b9\u6848\uff08\u50cf\u5168\u6392\u5217\u90a3\u6837\uff09\uff0c\u4e0d\u8981\u62c5\u5fc3\u53e6\u5916\u7684\u7279\u6b8a\u60c5\u51b5\uff0cgo ahead\u3002 <\/p>\n

*\u6805\u680f\u7684\u9762\u79ef\u8981\u5927\u4e8e0. <\/p>\n

*\u8f93\u51fa\u4fdd\u8bc1\u7b54\u6848\u5728longint\u8303\u56f4\u5185\u3002 <\/p>\n

*\u6574\u5757\u6728\u677f\u90fd\u8981\u7528\u5b8c\u3002 <\/p>\n

<\/p>\n

Input <\/strong><\/p>\n

*\u7b2c\u4e00\u884c\uff1a\u4e00\u4e2a\u6570n <\/p>\n

Output <\/strong><\/p>\n

*\u7b2c\u4e00\u884c\uff1a\u5408\u7406\u7684\u65b9\u6848\u603b\u6570 <\/p>\n

Sample Input <\/strong><\/p>\n<\/p>\n

Sample Output <\/strong><\/p>\n<\/p>\n

Source <\/strong><\/p>\n

\u8d44\u683c\u8d5b
\u997f\u3002\u3002\u8fd9\u4e2a\u672c\u6765\u662f\u8981\u7528Dp\u7684\u3002\u3002\u4f46\u6211\u5bb9\u65a5\u7528\u723d\u4e86\u3002\u3002\u76f4\u63a5\u4e0a\u5bb9\u65a5\u539f\u7406(*^__^*)
Code\uff1a <\/p>\n

#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstdlib>#include<cstdlib>#include<cstring>#include<string>#include<vector>#include<set>#include<queue>#include<map>#define rep(i,n) for(int i=0;i<n;i++)#define For(i,a,b) for(int i=a;i<=b;i++)#define tr(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)#define all(x) x.begin(),x.end()#define pb push_backusing namespace std;const int inf=~0U>>1,maxn=2600;typedef vector<int> vi;typedef vector<vi> vvi;typedef pair<int,int> ii;int n,dp[5][maxn]={0};typedef long long ll;ll WaySumTo(int a,int b){ if(a<0)return 0; ll ret=1;a+=–b; rep(i,b) ret*=a-i; rep(i,b) ret\/=i+1; return ret;}int main(){ \/\/freopen("in","r",stdin); cin>>n;int a=n\/2;if(a*2==n)–a; n-=4; cout<<WaySumTo(n,4)-4*WaySumTo(n-a,4)+6*WaySumTo(n-2*a,4)-4*WaySumTo(n-3*a,4)+WaySumTo(n-4*a,4)<<endl;}<\/p>\n

6\u8f93\u51fa\u8be6\u89e3\uff1aFarmer John\u80fd\u591f\u5207\u51fa\u6240\u6709\u7684\u60c5\u51b5\u4e3a: (1, 1, 1,3); (1, 1, 2, 2); (1, 1, 3, 1); (1, 2, 1, 2); (1, 2, 2, 1); (1, 3,1, 1);(2, 1, 1, 2); (2, 1, 2, 1); (2, 2, 1, 1); or (3, 1, 1, 1).\u4e0b\u9762\u56db\u79cd — (1, 1, 1, 3), (1, 1, 3, 1), (1, 3, 1, 1), and (3,1, 1, 1) – \u4e0d\u80fd\u591f\u7ec4\u6210\u4e00\u4e2a\u56db\u8fb9\u5f62.6 <\/p>\n","protected":false},"excerpt":{"rendered":"

[Usaco2008 Oct]\u5efa\u9020\u6805\u680f Time Limit:5000MS Memory Limit:65536KTotal Submit:6 Accepted:6 Case Time Limit:1000MS Description \u52e4\u594b\u7684Farmer John\u60f3\u8981\u5efa\u9020\u4e00\u4e2a\u56db\u9762\u7684\u6805\u680f\u6765\u5173\u4f4f\u725b\u4eec\u3002\u4ed6\u6709\u4e00\u5757\u957f\u4e3an\uff084<=n<=2500\uff09\u7684\u6728\u677f\uff0c\u4ed6\u60f3\u628a\u8fd9\u5757\u672c\u677f\u5207\u62104\u5757\u3002 \u8fd9\u56db\u5757\u5c0f\u6728\u677f\u53ef\u4ee5\u662f\u4efb\u4f55\u4e00\u4e2a\u957f\u5ea6\u53ea\u8981Farmer John\u80fd\u591f\u628a\u5b83\u4eec\u56f4\u6210\u4e00\u4e2a\u5408\u7406\u7684\u56db\u8fb9\u5f62\u3002\u4ed6\u80fd\u591f\u5207\u51fa\u591a\u5c11\u79cd\u4e0d\u540c\u7684\u5408\u7406\u65b9\u6848\u3002 \u6ce8\u610f\uff1a *\u53ea\u8981\u5927\u6728\u677f\u7684\u5207\u5272\u70b9\u4e0d\u540c\u5c31\u5f53\u6210\u662f\u4e0d\u540c\u7684\u65b9\u6848\uff08\u50cf\u5168\u6392\u5217\u90a3\u6837\uff09\uff0c\u4e0d\u8981\u62c5\u5fc3\u53e6\u5916\u7684\u7279\u6b8a\u60c5\u51b5\uff0cgo ahead\u3002 *\u6805\u680f\u7684\u9762\u79ef\u8981\u5927\u4e8e0. *\u8f93\u51fa\u4fdd\u8bc1\u7b54\u6848\u5728longint\u8303\u56f4\u5185\u3002 *\u6574\u5757\u6728\u677f\u90fd\u8981\u7528\u5b8c\u3002 Input *\u7b2c\u4e00\u884c\uff1a\u4e00\u4e2a\u6570n Output *\u7b2c\u4e00\u884c\uff1a\u5408\u7406\u7684\u65b9\u6848\u603b\u6570 Sample Input Sample Output Source \u8d44\u683c\u8d5b\u997f\u3002\u3002\u8fd9\u4e2a\u672c\u6765\u662f\u8981\u7528Dp\u7684\u3002\u3002\u4f46\u6211\u5bb9\u65a5\u7528\u723d\u4e86\u3002\u3002\u76f4\u63a5\u4e0a\u5bb9\u65a5\u539f\u7406(*^__^*) Code\uff1a #include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstdlib>#include<cstdlib>#include<cstring>#include<string>#include<vector>#include<set>#include<queue>#include<map>#define rep(i,n) for(int i=0;i<n;i++)#define For(i,a,b) for(int i=a;i<=b;i++)#define tr(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)#define all(x) x.begin(),x.end()#define pb push_backusing namespace std;const int inf=~0U>>1,maxn=2600;typedef vector<int> vi;typedef vector<vi> vvi;typedef […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/199"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=199"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/199\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=199"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=199"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=199"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}