本文主要是介绍hdu -4655 Cut Pieces，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
不知道你们看懂题解了没。。反正我是没看懂。。。
给定一个序列长度为n，序列内的数为a1……an.
则piece数最多的序列为a1,an,a2,a(n-1),a3,a(n-2).......
现在知道序列了，怎么求由这个序列产生的piece数呢？
假如n=4，序列为2 3 4 2。
我们从左往右计算piece数。
当序列只有a1=2时，piece数为2，即sum=2；
当序列加入a2=3，即序列为2 3：
因为第二块积木，可以涂三种颜色，而每当第二块积木涂一种颜色的时候，第一块积木可以涂sum种颜色，
即因为增加了第二块积木，第二块积木之前的积木总共产生了sum*a2个piece。
当放上第二块积木的时候，第二块积木产生了多少piece呢？
因为第二块积木产生的piece数只与第一块积木是否和其相等有关，所以，由第二块积木产生的piece数为min(a1,a2)*（max(a1,a2)-1）;
为什么是min(a1,a2)*（max(a1,a2)-1）呢?因为第二块积木若想因其增加piece数，只能是与前一块积木的颜色不想等，那么就是从1-a1中拿一个数和1-a2中拿一个数，
找这两个数不想等的数目，即为min(a1,a2)*（max(a1,a2）-1)；
所以序列为2 3的piece数为sum=sum*a2+min(a1,a2)*（max(a1,a2)-1）=10；
当序列加入a3=4,即序列为2 3 4：
因为增加了第三块积木，第三块积木之前的积木总共产生了sum*a3个piece。
当增加第三块积木之后，第三块积木产生了多少个piece呢？
当增加了第三块积木，第三块积木与第二块积木之间，由第三块积木产生的piece为min(a3,a2)*（max(a3,a2)-1）；
但是此时第二块积木之前有积木，第二块积木之前的积木总共有a1种情况，所以由第三块积木产生的piece为（min(a3,a2)*max(a3,a2)-1）*a1；
所以序列为2 3 4的piece数为sum=sum*a3+min(a3,a2)*（max(a3,a2)-1）*a1=58；
当序列加入a4=2,即序列为2 3 4 2：
因为增加了第四块积木，第四块积木之前的积木总共产生了sum*a4个piece。
当增加第四块积木之后，第四块积木产生了min(a3,a4)*（max(a3,a4)-1）*(a1*a2)；
所以序列为2 3 4 2的piece数为sum=sum*a4+min(a3,a4)*（max(a3,a4)-1）*(a1*a2)；
代码：
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define mm 1000000007
__int64 a[1000001];
__int64 b[1000001];
__int64 x[1000001];
__int64 jisuan(__int64 n)
{__int64 i;__int64 sum;x[0]=1;x[1]=a[0];for(i=2;i<n;i++)x[i]=x[i-1]*a[i-1],x[i]=x[i]%mm;sum=a[0];for(i=1;i<n;i++){sum=sum*a[i]%mm+((((a[i]>a[i-1]?a[i]:a[i-1])-1)*(a[i]<a[i-1]?a[i]:a[i-1]))%mm)*x[i-1]%mm;sum=sum%mm;}return sum;
}
int main()
{// freopen("data.in","r",stdin);// freopen("data.out","w",stdout);__int64 T,i,n;scanf("%I64d",&T);while(T--){scanf("%I64d",&n);for(i=0;i<n;i++){scanf("%I64d",&a[i]);b[i]=a[i];}sort(b,b+n);for(i=0;i<n;i++){if(i%2==0)a[i]=b[i/2];else a[i]=b[n-i/2-1];}__int64 sss;sss=jisuan(n);if(n<=0)sss=0;printf("%I64d\n",sss);}return 0;
}
这篇关于hdu -4655 Cut Pieces的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
