[2 차원 패 킷 기록 경로] 암흑 파괴 신

3119 단어 동적 계획
[url]http://openoj.awaysoft.com/JudgeOnline/problem.php?id=1634[/url]
[b][size=medium]
[align = center] [color = green] 암흑 파괴 신 [/ color] [/ align]
[color=blue]Description[/color]
심심 한 꼬마 x 가 디 아 블 로 I 를...
게임 의 주인공 은 n 개의 마법 이 있 습 니 다.
각 마법 은 몇 등급 으로 나 뉘 는데, i 번 째 마법 은 p [i] 개 등급 (0 포함 하지 않 음)
각 마법 의 각 레벨 마다 효과 치가 있 습 니 다. j 레벨 의 i 가지 마법 의 효과 치 는 w [i] [j] 입 니 다.
마법 진급 에 해당 하 는 마법 서 한 권 이 필요 합 니 다.
마법 서 를 구 매 하려 면 금화 가 필요 하 며, i 번 째 마법 서 의 가격 은 c [i] 입 니 다.
작은 x 는 m 개의 금화 밖 에 없다.
당신 의 임 무 는 작은 x 가 마법 서 를 어떻게 구 매 해 야 모든 마법 의 효과 치 와 최대 치 를 결정 할 수 있 는 지 도와 주 는 것 입 니 다.
시작 시 모든 마법 이 0 레벨 효과 치 0
[color=blue]Input[/color]
첫 줄 을 빈 칸 으로 나 눈 정수 n (0)
아래 n 줄 설명 n 개 마법
i + 1 줄 설명 i 번 째 마법 형식 은 다음 과 같다 (0
c[i] p[i] w[i][1] w[i][2] ... w[i][p[i]]
[color=blue]Output[/color]
첫 번 째 줄 은 하나의 정수, 즉 최대 효과 값 을 출력 합 니 다. (입력 데이터 와 최종 결 과 는 longint 범위 내 에서 보장 합 니 다)
나중에 n 줄 에서 프로젝트 를 출력 합 니 다:
i + 1 줄 에 정수 v [i] 가 있 습 니 다. i 번 째 마법 을 v [i] 급 으로 배우 기로 했 습 니 다.
수출 비용 이 가장 적은 그룹 이 있다 면
임의의 그룹 을 더 풀 면
[color=blue]Sample Input[/color]
3 10
1 3 1 2 2
2 3 2 4 6
3 3 2 1 10
[color=blue]Sample Output[/color]
11
1
0
3
[/size][/b]

#include
#include
#include
#include
#include
//#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define inf 0x3fffffff

int dp[105][505], w[105], M, num, mark[105][505], v[105], c[105];

void gp1_pack (int i, int cost) //
{
int j, k;
for (j = 1; j <= M; j++)
{
for (k = 0; k <= num && j >= k*cost; k++)
{
if (dp[i][j] < dp[i-1][j-k*cost] + w[k])
{
dp[i][j] = dp[i-1][j-k*cost] + w[k];
mark[i][j] = k; // 【k: i k 】
}
}
}
}

int main()
{
int n, i, j, maxs, vj;
while (~scanf ("%d%d", &n, &M))
{
w[0] = 0;
for (i = 1; i <= n; i++)
{
scanf ("%d%d", c+i, &num);
for (j = 1; j <= num; j++)
scanf ("%d", w+j);
gp1_pack (i, c[i]); //
}
maxs = 0;
for (j = M; j >= 0; j--) //
if (maxs <= dp[n][j])
maxs = dp[n][j], vj = j;
j = vj; //
for (i = n; i > 0; i--)
{
v[i] = mark[i][j]; //
j = j - c[i] * v[i]; //
}
printf ("%d
", maxs);
for (i = 1; i <= n; i++) //
printf ("%d
", v[i]);
}
return 0;
}

좋은 웹페이지 즐겨찾기