Codeforces 148E Porcelain(예처리+다중 백팩)
3319 단어 codeforces다중 배낭
time limit per test:3 seconds
memory limit per test:256 megabytes
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 onn 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 ofm shrieks can inflict on the collection of porcelain.
Input
The first line of input data contains two integersn (1 ≤ n ≤ 100) andm (1 ≤ m ≤ 10000). The nextn lines contain the values of the items on the shelves: the first number gives the number of items on this shelf (an integer between1 and100, inclusive), followed by the values of the items (integers between1 and100, 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 leastm.
Output
Output the maximal total value of a tantrum of m shrieks.
Sample test(s)
Input
2 3
3 3 7 2
3 4 1 5
Output
15
Input
1 3
4 4 3 1 2
Output
9
Note
In the first case there are two shelves, each with three items. To maximize the total value of the items chosen, one can take two items from the left side of the first shelf and one item from the right side of the second shelf.
In the second case there is only one shelf, so all three items are taken from it — two from the left side and one from the right side.
제목 링크:http://codeforces.com/contest/148/problem/e
제목 대의: n층의 숫자를 주면 모두 m번을 뽑아야 하며, 매번 숫자를 뽑을 때마다 임의의 층의 가장 왼쪽 또는 가장 오른쪽에서만 뽑을 수 있다.
제목 분석: 각 층에서 양쪽에서 j(j<=m)개의 가능한 최대치를 미리 처리하고 그 다음은 일반적인 다중 가방 문제입니다.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int sum[105], ma[105], dp[10005];
int main()
{
int n, m;
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++)
{
int num;
scanf("%d", &num);
for(int j = 1; j <= num; j++)
{
int tmp;
scanf("%d", &tmp);
sum[j] = sum[j - 1] + tmp; //
}
//
memset(ma, 0, sizeof(ma));
for(int j = 0; j <= num; j++)
for(int k = 0; k <= j; k++)
ma[j] = max(ma[j], sum[k] + sum[num] - sum[num + k - j]);
printf("
");
//
for(int j = m; j >= 1; j--)
for(int k = 1; k <= min(j, num); k ++)
dp[j] = max(dp[j], dp[j - k] + ma[k]);
}
printf("%d
", dp[m]);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces Round #715 Div. 2C The Sports Festival: 구간 DP전형구간 DP의 초전형. 이하, 0-indexed. 입력을 정렬하여 어디서나 시작하고 최적으로 좌우로 계속 유지하면 좋다는 것을 알 수 있습니다. {2000})$의 주문이 된다. 우선, 입력을 소트하여 n개의 요소를 $...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.