Problem cowrun: The Cow Run [Chris Tzamos, 2006]<\/p>\n
The N (1 <= N <= 1,000) cows have escaped from the farm and have
gone on a rampage. Each minute a cow is outside the fence, she
causes one dollar worth of damage. Farmer John must visit each one
to install a halter that will calm the cow and stop the damage.<\/p>\n
Happily, the cows are positioned in a straight line on a road outside
the farm. FJ can see each of them and knows every cow i’s unique
coordinates (-500,000 <= P_i <= 500,000, P_i != 0) relative to the
gate (position 0) where FJ starts.<\/p>\n
FJ moves at one unit of distance per minute and can install a halter
instantly. Determine the order that FJ should visit the cows so he
can minimize the total cost of the damage; report the minimum total
damage.<\/p>\n
PROBLEM NAME: cowrun<\/p>\n
INPUT FORMAT:<\/p>\n
* Line 1: A single integer: N<\/p>\n
* Lines 2..N+1: Line i+1 contains a single integer: P_i<\/p>\n
SAMPLE INPUT (file cowrun.in):<\/p>\n
4
-2
-12
3
7<\/p>\n
INPUT DETAILS:<\/p>\n
Four cows placed in positions: -2, -12, 3, and 7.<\/p>\n
OUTPUT FORMAT:<\/p>\n
* Line 1: The minimum total cost of the damage.<\/p>\n
SAMPLE OUTPUT (file cowrun.out):<\/p>\n
50<\/p>\n
OUTPUT DETAILS:<\/p>\n
The optimal visit order is -2, 3, 7, -12. FJ arrives at position
-2 in 2 minutes for a total of 2 dollars in damage for that cow.<\/p>\n
He then travels to position 3 (distance: 5) where the cumulative
damage is 2 + 5 = 7 dollars for that cow.<\/p>\n
He spends 4 more minutes to get to 7 at a cost of 7 + 4 = 11 dollars
for that cow.<\/p>\n
Finally, he spends 19 minutes to go to -12 with a cost of 11 + 19
= 30 dollars.<\/p>\n
The total damage is 2 + 7 + 11 + 30 = 50 dollars.<\/p>\n
\u8fd9\u9053\u6709\u70b9\u50cf\u5251\u4e4b\u4fee\u70bc\uff0c\u5c31\u662f\u8ba9\u5976\u725b\u51b7\u9759\u4e0d\u7528\u65f6\u95f4\u3002FJ\u6240\u5230\u4e4b\u5904\u5c31\u662f\u5976\u725b\u5b89\u9759\u4e4b\u5904\u3002<\/p>\n
\u7531\u4e8eFJ\u6700\u521d\u5728\u539f\u70b9\uff0c\u53ea\u80fd\u5de6\u53f3\u505a\u5f80\u8fd4\u8fd0\u52a8\uff08\u4e00\u79f0\u6d3b\u585e\u8fd0\u52a8<\/strong>\uff09\u3002\u6240\u4ee5\u5976\u725b\u5b89\u9759\u7684\u533a\u57df\u5c31\u662f\u4e00\u6761\u5305\u62ec\u539f\u70b9\u7684\u7ebf\u6bb5\u3002<\/p>\n \u6240\u4ee5\u8bbe\u8ba1\u72b6\u6001dp[i][j][k]\u3002\u5176\u4e2di\u8868\u793aFJ\u5728\u8d1f\u534a\u8f74\u5b89\u6170\u4e86i\u4e4b\u725b\uff0cj\u8868\u793aFJ\u5728\u6b63\u534a\u8f74\u5b89\u6170\u7684\u725b\u6570\u3002k=0\u8868\u793aFJ\u6700\u7ec8\u4f4d\u7f6e\u5728\u6700\u5de6\u8fb9\u7684\u51b7\u9759\u7684\u725b\uff0ck=1\u8868\u793aFJ\u6700\u7ec8\u5728\u6700\u53f3\u8fb9\u7684\u51b7\u9759\u7684\u725b\u3002<\/p>\n \u8fd9\u6837\u5b50\u5c31\u6613\u5f97\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\uff1a<\/p>\n dp[i][j][0] = min( dp[i-1][j][0] + (n-i-j+1) * (a1[i-1]-a1[i]) , dp[i-1][j][1] + (n-i-j+1) * (a2[j]-a1[i]) )<\/p>\n dp[i][j][1] = min( dp[i][j-1][0] + (n-i-j+1) * (a2[j]-a1[i]) , dp[i][j-1][1] + (n-i-j+1) * (a2[j]-a2[j-1]) )<\/p>\n \u8fb9\u754c\u6761\u4ef6\u5c31\u662f i=0 \u6216 j=0 \u7684\u65f6\u5019\uff0c\u8fd9\u4e2a\u65f6\u5019\u7684\u503c\u662f\u663e\u7136\u7684\u3002<\/p>\n \u8fd9\u4e2a\u4f3c\u4e4e\u662f\u6211\u7b2c\u4e8c\u4e2a\u975e\u7eaf\u6c34\u9898\u7684C++\u7a0b\u5e8f\u3002C++\u771f\u662f\u7b80\u6d01\u7f8e\u4e3d\u554a\uff0c\u4f46\u662f\u5982\u679c\u7f16\u7a0b\u4e60\u60ef\u4e0d\u597d\u7684\u8bddC++\u4fbf\u4f1a\u53d8\u5f97\u6bd4PASCAL\u7325\u7410100\u500d\u3002<\/p>\n \u9898\u76ee\u63cf\u8ff0 Problem cowrun: The Cow Run [Chris Tzamos, 2006] T […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[13],"tags":[131,344],"class_list":["post-362","post","type-post","status-publish","format-standard","hentry","category-13","tag-131","tag-344"],"_links":{"self":[{"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/362","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=362"}],"version-history":[{"count":0,"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/362\/revisions"}],"wp:attachment":[{"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=362"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=362"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=362"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}\u6211\u7684\u7a0b\u5e8f<\/h3>\n
\/*\nID: sinya1\nPROG: cowrun\nLANG: C++\n*\/\n\n# include <iostream>\nusing namespace std;\n\nconst int maxn=1001;\nint i,j,n,n1\/*FJ\u5de6\u8fb9\u7684\u725b\u6570*\/,n2\/*FJ\u53f3\u8fb9\u7684\u725b\u6570*\/;\nint t[maxn]\/*\u539f\u59cb\u6570\u636e*\/,a1[maxn]\/*FJ\u5de6\u8fb9\u7684\u725b*\/,a2[maxn]\/*FJ\u53f3\u8fb9\u7684\u725b*\/;\nint dp[maxn][maxn][2];\n\nvoid qsort(const int x,const int y){\n int i=x,j=y,sign=t[(x+y)>>1];\n do{\n while (t[i]<sign) i++;\n while (t[j]>sign) j--;\n if (i<=j) swap(t[i++],t[j--]);\n }while (i<=j);\n if (x<j) qsort(x,j);\n if (i<y) qsort(i,y);\n}\n\nvoid init(){\n scanf(\"%d\",&n);\n for (i=0;i<n;i++) scanf(\"%d\",&t[i]);\n qsort(0,n-1);\n\n a1[0]=0;n1=1;\n for (i=0;i<n&&t[i]<0;i++) a1[n1++]=t[i];\n for (i=1;i<=n1>>1;i++) swap(a1[i],a1[n1-i]);\n a2[0]=0;n2=1;\n for (i=n1-1;i<n;i++) a2[n2++]=t[i];\n}\n\nvoid work(){\n dp[0][0][0]=dp[0][0][1]=0;\n for (j=1;j<n2;j++) {\n dp[0][j][1]=dp[0][j-1][1]+(n-j+1)*(a2[j]-a2[j-1]);\n dp[0][j][0]=dp[0][j][1]+(n-j)*(a2[j]);\n }\n for (i=1;i<n1;i++) {\n dp[i][0][0]=dp[i-1][0][0]+(n-i+1)*(a1[i-1]-a1[i]);\n dp[i][0][1]=dp[i][0][0]+(n-i)*(-a1[i]);\n for (j=1;j<n2;j++){\n dp[i][j][0]=min(\n dp[i-1][j][0]+(n-i-j+1)*(a1[i-1]-a1[i]),\n dp[i-1][j][1]+(n-i-j+1)*(a2[j]-a1[i])\n );\n dp[i][j][1]=min(\n dp[i][j-1][0]+(n-i-j+1)*(a2[j]-a1[i]),\n dp[i][j-1][1]+(n-i-j+1)*(a2[j]-a2[j-1])\n );\n }\n }\n printf(\"%d\\n\",min(dp[n1-1][n2-1][0],dp[n1-1][n2-1][1]));\n}\n\nint main(){\n freopen(\"cowrun.in\",\"r\",stdin);\n freopen(\"cowrun.out\",\"w\",stdout);\n\n init();\n work();\n return 0;\n}<\/pre>\n","protected":false},"excerpt":{"rendered":"