HDU 1494 카트라이더(세그먼트 DP)

제목 대의: 제목의 뜻에 주의하라. 두 개의 에너지 카드가 가득 차면 두 개의 에너지 카드는 여전히 존재한다. 단지 현재 새로운 카드가 생기지 않고 현재의 카드의 에너지가 0이 될 뿐이다.방금 이 문제를 보니 매우 까다롭다. 단락을 나누고 에너지의 집합도 있을 것이다.동그라미를 치다.그러면 dp[i][j]로 첫 번째 단락에 에너지 j가 있음을 나타낼 수 있다.에너지점이나 단락으로 현재의 상태 전환을 분석하고 마지막으로 링을 바꿀 때 현재의 상태를 다음 상태로 전환하면 된다.

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<queue>
#include<map>
#include<stack>
#define L1 long long
#define L2 int
#define inf 0x3f3f3f3f
using namespace std;
const int m1=1001000;
const int m2=1010;

int a[1010],b[1010];
int dp[10010][16];
int main()
{
    int n,m,i,j,k,l,mi;
    while(~scanf("%d%d",&l,&n))
    {
        memset(dp,inf,sizeof(dp));
        for(i=1; i<=l; i++)
            scanf("%d",&a[i]);
        for(i=1; i<=l; i++)
            scanf("%d",&b[i]);
        dp[0][0]=0;
        for(k=1; k<=n; k++)
        {
            for(i=1; i<=l; i++)
            {
                for(j=0; j<15; j++)
                {
                    if(j==0)
                        dp[i][j]=dp[i-1][j+5] +b[i];
                    else if(j==10){
                        dp[i][j]=min(dp[i-1][j-1]+a[i],dp[i-1][14]+a[i]);
                    }
                    else if(j>=1&&j<=9)
                        dp[i][j]=min(dp[i-1][j-1]+a[i],dp[i-1][j+5]+b[i]);
                    else
                        dp[i][j]=dp[i-1][j-1]+a[i];
                }
            }
            for(i=0;i<15;i++){
                dp[0][i]=dp[l][i];
            }
        }

        mi=0x3f3f3f3f;
        for(i=0; i<15; i++)
            mi=min(mi,dp[l][i]);
        printf("%d
",mi);
    }
}