【題目描述】

有n個櫻桃排成一列，第i個櫻桃的甜度為v[i]，你要把n個櫻桃分成若干組，其中每一組的櫻桃必須相鄰。每一組櫻桃的美味度為(sum-T)^2 ， 其中sum是這組櫻桃的甜度之和，T為輸入給定的系數(shù)。

一組方案的美味度為每一組的美味度之和。

求可行方案最小的美味度。

【輸入格式】

輸入文件cherry.in

第一行兩個正整數(shù) n，T。

第二行n個整數(shù)，第i個整數(shù)是第i個櫻桃的甜度，v[i]。

【輸出格式】

輸出文件cherry.out

一行一個非負(fù)整數(shù)，為最小美味度。

【樣例輸入】

5 5

3 5 2 1 6

【樣例輸出】

【數(shù)據(jù)范圍】

對于50%的數(shù)據(jù)滿足n<=10,T<=1000,v[i]<=10

對于70%的數(shù)據(jù)滿足n<=100

對于所有數(shù)據(jù)，n<=10^3,T<=1000,v[i]<=10

每組櫻桃必須相鄰，使美味度之和最小。很容易聯(lián)想到其實和石子合并差不多，可以用區(qū)間劃分來做。但是看一眼數(shù)據(jù)1000，n³的復(fù)雜度，應(yīng)該會tle（事實證明就是會T了）。

那么應(yīng)該怎么樣優(yōu)化呢，我們可以考慮，不采用區(qū)間劃分，我們枚舉有多少個櫻桃，然后再枚舉這個櫻桃和最后幾個櫻桃組成一組。

具體實現(xiàn)的話，我們要整一個前綴和（求甜度要用），我們可以用f【i】表示前i個櫻桃的最少甜度那么，用j來枚舉與第i個櫻桃組成一組的櫻桃的數(shù)量的開始，那么狀態(tài)轉(zhuǎn)移方程就出來了

f[i]=min(f[i],f[j]+(sum[i]-sum[j-1]-t)*(sum[i]-sum[j-1]-t));

最后附上代碼

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 using namespace std;
 5 int n,a[1010],f[1010],t,sum[1010];
 6 int main()
 7 {
 8     scanf("%d%d",&n,&t);
 9     memset(f,0x3f,sizeof(f));
10     for(int i=1;i<=n;++i)
11     {
12         scanf("%d",&a[i]);
13         sum[i]=sum[i-1]+a[i];
14     }
15     
16     f[1]=(a[1]-t )*(a[1]-t);
17     f[0]=0;
18     for(int i=2;i<=n;++i)
19     {
20         for(int j=i-1;j>=0;--j)
21         {
22             f[i]=min(f[i],f[j]+(sum[i]-sum[j]-t)*(sum[i]-sum[j]-t));
23         }
24     }
25     printf("%d",f[n]);
26     return 0;
27 }

總結(jié)

以上是生活随笔為你收集整理的摘樱桃的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。