poj2385

动态规划

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;

#define maxn 1005
#define maxw 35

int n, w;
int apple[maxn][2];
int f[maxw][maxn][2];

int main()
{
    //freopen("t.txt", "r", stdin);
    scanf("%d%d", &n, &w);
    memset(apple, 0, sizeof(apple));
    for (int i = 1; i <= n; i++)
    {
        int a;
        scanf("%d", &a);
        apple[i][a - 1] = 1;
    }
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; i++)
        f[0][i][0] = f[0][i - 1][0] + apple[i][0];
    for (int i = 1; i <= w; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            f[i][j][0] = max(f[i][j - 1][0] + apple[j][0], f[i - 1][j - 1][1] + apple[j][0]);
            f[i][j][1] = max(f[i - 1][j - 1][0] + apple[j][1], f[i][j - 1][1] + apple[j][1]);
        }
    }

    printf("%d\n", max(f[w][n][0], f[w][n][1]));
    return 0;
}