首页 > 分享 > POJ 3253 Fence Repair

POJ 3253 Fence Repair

花匠小妙招
2025-01-18 09:11

农夫约翰想修一小段牧场周围的篱笆。他测量了栅栏，发现他需要N（1≤N≤20000）块木板，每块木板都有一些整数长度的Li（1≤Li≤50000）单位。然后，他买了一块长木板，长度刚好能锯进N块木板（即，木板的长度是长度Li的总和）。FJ忽略了“切口”，即锯切时锯屑所损失的额外长度；你也应该忽略它。

福建悲哀地意识到，他没有一个锯与削减木材，所以他大摇大摆地到农民唐的农场与这长板，礼貌地问他是否可以借用一把锯。

农民唐，一个秘密资本家，不借给FJ一把锯子，而是提出向农民约翰收取木板上每一个N-1切口的费用。砍一块木头的费用正好等于它的长度。切割一块长21的木板要花21美分。

农夫唐让农夫约翰决定切割木板的顺序和地点。帮助农场主约翰确定他能花多少钱来制作木板。福建知道，他可以削减董事会在不同的顺序，这将导致不同的费用，因为产生的中间木板是不同的长度。

输入
第1行：一个整数N，木板的数量
第2行。。N+1：每行包含一个整数，用于描述所需木板的长度
输出
第1行：一个整数：他必须花费最少的钱来进行N-1次削减
样本输入
3
8
5
8
样本输出
34个
暗示
他想把一块21长的木板切成8、5和8长的几块。
原来的棋盘是8+5+8=21。第一次切割要花21英镑，应该用来把木板切成13和8块。第二次削减将花费13，并应用于削减13成8和5。这将花费21+13=34。如果把21分为16分和5分，第二次削减将花费16分，总共37分（超过34分）。
代码

#include<stdio.h> #include<algorithm> using namespace std; int a[20010]; int main() {int n,i,j;long long s=0;//一定要开long long 类型，这里真坑scanf("%d",&n);for(i=0;i<n;i++){scanf("%d",&a[i]);}sort(a,a+n);int t;for(i=0;i<n-1;i++)//注意n-1 因为i=n-2时后面的a[i+1]就是a[n-1]刚好加到a[n-1]{ t=a[i]+a[i+1];s=s+t;for( j=i+2;j<n;j++)//注意i+2 因为a[i]与a[i+1]结合起来了{if(a[i]<t) a[j-1]=a[j];//向前推进，如3 4 5 6,3与4结合成7，a[j-1]->5，排好后为3 5 6 7 其中3无用了，7就为j==n情况 else { a[j-1]=t; break;//找到位置后跳出 }} if(j==n)//注意 j==n情况 a[j-1]=t;}printf("%lldn",s);return 0; }

1234567891011121314151617181920212223242526272829303132333435