(UVA) 1231 - ACORN

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3672

Tips : DP

#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;

const int MAX_N = 2006;

int dp[MAX_N][MAX_N];
int mx[MAX_N];
int cnt[MAX_N][MAX_N];

int main () {
    int T;
    while (scanf("%d",&T) != EOF) {
        if (T == 0) break;
        while (T--) {
            int n,m,f;
            scanf("%d %d %d",&n,&m,&f);
            memset(cnt,0,sizeof(cnt));
            memset(dp,0,sizeof(dp));
            memset(mx,0,sizeof(mx));
            for (int x=1;n>=x;x++) {
                int k;
                scanf("%d",&k);
                while (k--) {
                    int i;
                    scanf("%d",&i);
                    cnt[x][i]++;
                }
            }
            for (int j=1;m>=j;j++) {
                for (int i=1;n>=i;i++) {
                    if (j-f > 0) dp[i][j] = cnt[i][j] + max(mx[j-f],dp[i][j-1]);
                    else dp[i][j] = cnt[i][j] + dp[i][j-1];
                    //cout<<"dp["<<i<<"]["<<j<<"] = "<<dp[i][j]<<endl;
                    mx[j] = max(mx[j],dp[i][j]);
                }
            }
            int ans=-1;
            for (int i=1;n>=i;i++) {
                ans = max(ans,dp[i][m]);
            }
            printf("%d\n",ans);
        }
    }
}