Magic Tree 水dp 错题！

Magic Tree

Time Limit 1000ms Memory Limit 65536K

description

Every acmer dream for gold medal. Fotunately,there are two magic trees (which are conveniently numbered 1 and 2) in our campus, each full of gold medal. The trees are very high, so we can not touch the gold medal when they are in the tree but wait for them to fall. However, we must catch them in the air since the gold medal disappear when they hit the ground. Each minute, one of the two magic trees drops a medal. we can catch an medal if we are standing under a tree from which one falls. The magic tree 1 is near by the magic tree 2.So we can walk between the two trees quickly (in much less than a minute), we can stand under only one tree at any time. Moreover, we are not willing to walk back and forth between the trees endlessly (and thus misses some gold medal).  Medal fall (one each minute) for T (1 ≤ T ≤ 1,000) minutes. We are willing to walk back and forth at most W (1 ≤ W ≤ 30) times. Given which tree will drop an medal each minute, determine the maximum number of medal which we can catch. We starts at magic tree 1.

input

Line 1: Two space separated integers: T and W Lines 2~T+1: 1 or 2, the tree that will drop a medal each minute.

output

Line 1: The maximum number of medal we can catch without running more than W times.

sample_input

7 2 2 1 1 2 2 1 1

sample_output

6

hint

INPUT DETAILS:  Seven medal fall - one from tree 2, then two in a row from tree 1, then two in a row from tree 2, then two in a row from tree 1.We are willing to walk from one tree to the other twice. OUTPUT DETAILS:  We can catch six medals by staying under tree 1 until the first two have dropped, then moving to tree 2 for the next two, then returning back to tree 1 for the final two.

------------------------------------------------------------------

 We starts at magic tree 1.

考虑了这一句话反而错了。不考虑起点就能A了。

------------------------------------------------------------------

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int f[2111][5][55];
int a[2111][5];

int T,W;

int dfs(int time,int tree,int jump)
{
    if (f[time][tree][jump]!=-1) return f[time][tree][jump];
    int ret=0;
    if (time<T)
    {
        ret=dfs(time+1,tree,jump);
        if (jump>0)
        {
            if (tree==1)
            {
                ret=max( ret, dfs(time+1,2,jump-1) );
            }
            else if (tree==2)
            {
                ret=max( ret, dfs(time+1,1,jump-1) );
            }
        }
    }
    f[time][tree][jump]=ret+a[time][tree];
    return f[time][tree][jump];
}

int main()
{

    while (~scanf("%d%d",&T,&W))
    {
        memset(a,0,sizeof(a));
        memset(f,-1,sizeof(f));
        for (int i=1;i<=T;i++)
        {
            int t;
            scanf("%d",&t);
            a[i][t]=1;
        }
        int ans=max(dfs(0,1,W), dfs(0,2,W));
        printf("%d\n",ans);
    }
    return 0;
}