程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> CodeForces 6D Lizards and Basements 2

CodeForces 6D Lizards and Basements 2

編輯：C++入門知識

CodeForces 6D Lizards and Basements 2

算是簡單DP了，一開始竟沒看出來，醉了。

首先，對於當前位置site，需知道site-1處丟了pre個，site處丟了now個火球，然後枚舉site+1處的情況。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#pragma comment(linker, "/STACK:1024000000,1024000000")
#define EPS (1e-6)
#define LL long long
#define ULL unsigned long long
#define _LL __int64
#define INF 0x3f3f3f3f
#define Mod 676

using namespace std;

int h[20],dp[20][20][20],next[20][20][20];

int n,a,b;

int dfs(int site,int pre,int now)
{
    if(dp[site][pre][now] != INF)
        return dp[site][pre][now];

    if(site == n-1)
    {
        if(h[site] >= pre*b+now*a || h[site+1] >= now*b)
            return dp[site][pre][now] = 1 + INF;
        return dp[site][pre][now] = now;
    }

    dp[site][pre][now] = 0;

    int tmp = INF;

    for(int i = 0;i <= 16; ++i)
    {
        if(h[site] >= (pre+i)*b + now*a)
            continue;
        if(now + dfs(site+1,now,i) < tmp)
        {
            tmp = now + dfs(site+1,now,i);
            next[site][pre][now] = i;
        }
    }

    return dp[site][pre][now] = tmp;
}

int main()
{
    int i;

    scanf("%d %d %d",&n,&a,&b);

    for(i = 1;i <= n; ++i)
        scanf("%d",&h[i]);

    memset(dp,INF,sizeof(dp));

    int Min = INF,pos;

    for(int i = (h[1]+b)/b;i <= 16; ++i)
        if(dfs(2,0,i) < Min)
            Min = dfs(2,0,i),pos = i;

    printf("%d\n",Min);

    int ans[20] = {0};

    int tmp,pre = 0,now = pos;

    for(i = 2;i < n; ++i)
    {
        ans[i] = now;
        tmp = next[i][pre][now];
        pre = now;
        now = tmp;
    }

    for(i = 1;i <= n; ++i)
        while(ans[i]--)
            printf("%d ",i);

    return 0;
}