CodeForces 148E(动态规划)

骑猪看日落 2022-06-04 06:51 191阅读 0赞

问题描述:

During her tantrums the princess usually smashes some collectable porcelain. Every furious shriek is accompanied with one item smashed.

The collection of porcelain is arranged neatly on n shelves. Within each shelf the items are placed in one row, so that one can access only the outermost items — the leftmost or the rightmost item, not the ones in the middle of the shelf. Once an item is taken, the next item on that side of the shelf can be accessed (see example). Once an item is taken, it can’t be returned to the shelves.

You are given the values of all items. Your task is to find the maximal damage the princess’ tantrum of m shrieks can inflict on the collection of porcelain.

Input

The first line of input data contains two integers n (1 ≤ n ≤ 100) and m (1 ≤ m ≤ 10000). The next n lines contain the values of the items on the shelves: the first number gives the number of items on this shelf (an integer between 1 and 100, inclusive), followed by the values of the items (integers between 1 and 100, inclusive), in the order in which they appear on the shelf (the first number corresponds to the leftmost item, the last one — to the rightmost one). The total number of items is guaranteed to be at least m.

Output

Output the maximal total value of a tantrum of m shrieks.

Example

  1. 2 3
  2. 3 3 7 2
  3. 3 4 1 5

15

题目题意:给我们我们n排数字,每排数字m[i]个,我们每次只能从最左端和最右端拿数字,拿走了就消失,问我们拿到的最大的数字和。

题目分析:因为拿数字的限制导致问题变得复杂,我们先处理出每一行拿i个数字的最大和,限制就没有了。

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<cmath>
  5. using namespace std;
  6. const int maxn=1e4+10;
  7. int sum[maxn],ma[105][maxn],dp[105][maxn],m[105];
  8. int main()
  9. {
  10. int n,num;
  11. while (scanf("%d%d",&n,&num)!=EOF) {
  12. for (int i=1;i<=n;i++) {
  13. scanf("%d",&m[i]);
  14. for (int j=1;j<=m[i];j++) {
  15. scanf("%d",&sum[j]);
  16. sum[j]=sum[j-1]+sum[j];
  17. }
  18. for (int k=1;k<=m[i];k++) {
  19. for (int j=0;j<=k;j++) {
  20. ma[i][k]=max(ma[i][k],sum[j]+sum[m[i]]-sum[m[i]+j-k]);//保存每一行拿k个数字的最大和
  21. }
  22. }
  23. }
  24. for (int i=1;i<=n;i++) {
  25. for (int j=num;j>=1;j--) {//必须逆向,为了避免重复拿数字
  26. for (int k=0;k<=m[i];k++) {
  27. if (j-k>=0)
  28. dp[i][j]=max(dp[i][j],dp[i-1][j-k]+ma[i][k]);
  29. }
  30. }
  31. }
  32. printf("%d\n",dp[n][num]);
  33. }
  34. return 0;
  35. }

发表评论

表情:
评论列表 (有 0 条评论,191人围观)

还没有评论,来说两句吧...

相关阅读

    相关 CodeForces1154E

    [CodeForces1154E][] 题意就是有两个教练,每个教练轮流操作,每次操作会选取所有未被选取的学生中能力值最高的那一个并把这个学生向左向右各\\(k\\)个学生

    相关 Codeforces 353E 贪心

    题意:给你一张有向图,第i条边连接i号点和(i + 1) % n号点,问最多可以选择多少个点,使得这些点互相不可达。 思路:容易发现,如果某个边的集合点的数目大于等于2,那么