剑圣的逃跑

描述

在一场ORC对NightElf比赛中（ORC必胜!），ORC全军覆没，只留下英雄--剑圣。
已知这个地图上有很多分叉，而剑圣正好在最顶端。在每个分叉处有敌人的军队封锁。设剑圣在i行j列，则他可以到达i+1行j列，i+1行j+1列，i+1行j+2列。每支敌人的军队的力量不同。剑圣可以使用魔法“疾风步”（剑圣的保命魔法）来通过一个关卡而不用受到伤害。剑圣需要你来找出一条路线，使他受到的伤害最少。

输入

第一行为关卡层数n（n<200）和剑圣可以使用“疾风步”的次数q(q<=n)。
第二行为剑圣的初始生命m(m<32767)。
以下n行为地图上军队力量（整数）的描述（若某个关卡上的军队力量为p，则剑圣不用“疾风步”时通过此关卡须受到p点伤害）。

输出

一行，若剑圣仍活着则输出他剩余的生命值，否则输出“DEAD”。

样例

输入

3 1
10
1
1 2 3
1 2 3 4 5

输出

8

#include<bits/stdc++.h>
using namespace std;
int a[201][401],n,f[201][401][201],m,q,ans=INT_MAX;
int main() {
    scanf("%d%d",&n,&q);
    scanf("%d",&m);
    memset(f,127/3,sizeof(f));
    for(int i=1; i<=n; i++)
        for(int j=1; j<=i*2-1; j++)
            scanf("%d",&a[i][j]);
    f[1][1][0]=a[1][1];
    f[1][1][1]=0;
    for(int i=2; i<=n; i++)
        for(int j=1; j<=i*2-1; j++)
            for(int k=0; k<=q; k++) {
                f[i][j][k]=min(f[i-1][j][k]+a[i][j],f[i][j][k]);
                f[i][j][k]=min(f[i-1][j-1][k]+a[i][j],f[i][j][k]);
                f[i][j][k]=min(f[i-1][j-2][k]+a[i][j],f[i][j][k]);
                f[i][j][k]=min(f[i-1][j][k-1],f[i][j][k]);
                f[i][j][k]=min(f[i-1][j-1][k-1],f[i][j][k]);
                f[i][j][k]=min(f[i-1][j-2][k-1],f[i][j][k]);
            }
    for(int i=1; i<=2*n-1; i++)
        ans=min(ans,f[n][i][q]);
    if(m-ans>0)
        printf("%d
",m-ans);
    else
        printf("DEAD
");
    return 0;
}