Porcelain KC的瓷器

2022-09-22 18:13:02 字數 1585 閱讀 8546

\(kc\)來到了一個盛產瓷器的國度。他來到了一位商人的店鋪。在這個店鋪中,\(kc\)看到了一個有\(n\)

\((1<=n<=100)\)排的櫃子,每排都有一些瓷器,每排不超過\(100\)個。那些精美的藝術品使\(kc\)一下心動了,決定從\(n\)排的商品中買下\(m\)

\((1<=m<=10000)\)個瓷器。

這個商人看\(kc\)的臉上長滿了痘子,就像苔蘚一樣,跟精美的瓷器相比相差太多,認為這麼精緻的藝術品被這樣的人買走藝術價值會大打折扣。商人感到不爽,於是規定每次取商品只能取其中一排的最左邊或者最右邊那個,想為難\(kc\)。

現在\(kc\)又獲知每個瓷器的價值(用一個不超過\(100\)的正整數表示),他希望取出的\(m\)個商品的總價值最大。

輸入檔案的第一行包括兩個正整數n,m;

接下來2到n+1行,第i行第一個數表示第i排櫃子的商品數量si,接下來si個數表示從左到右每個商品的價值。

輸出檔案只有一個正整數,即m個商品最大的總價值。

2 3

3 3 7 2

3 4 1 5

1 3

4 4 3 1 2

15
9
對於10%的資料,si=1,1<=i<=n。

對於另外10%的資料,n=1.

設\(sum[i][j]\)代表第\(i\)排的前\(j\)個的和

再設\(dis[i][j]\)代表第\(i\)排選\(j\)個的最大值

這個的動態轉移方程就是\(dis[i][j] = sum[i][k] + (sum[i][a[i]] - sum[i][a[i] - (j - k)])\)

再再設\(f[i][j]\)代表前\(i\)排選了\(j\)個的最大值

動態轉移方程是\(f[i][j] = f[i][j - k] + dis[i][k]\)

#include#include#include#includeusing namespace std;

int a[505][10005], s[505][10005], dis[505][10005], f[505][10005];

int n, m;

int main()

}for(int i = 1; i <= n; ++i)

for(int j = 1; j <= a[i][0]; j++)

for(int k = 0; k <= j; ++k)

dis[i][j] = max(dis[i][j], s[i][k] + s[i][a[i][0]] - s[i][a[i][0] - j + k]);

for(int i = 1; i <= n; ++i)

for(int j = 1; j <= m; ++j)

for(int k = 0; k <= min(j, a[i][0]); ++k)

f[i][j] = max(f[i][j], f[i - 1][j - k] + dis[i][k]);

printf("%d", f[n][m]);

return 0;

}

蒟蒻kc的垃圾數列

在某教練的強迫之下,我一個蒟蒻居然出題了!!!出題了!!! 資料太水別找我qwq 好的,jl說好的一題100快拿來 首先,給你一個空的長度為n的序列 廢話 然後,你有一系列神奇操作,好吧好吧,只有一個,那就是 l r k d 給出一個長度等於r l 1的等差數列,首項為k,公差為d,並將它對應加到a...