BZOJ 3997 组合数学

好厉害。

注意到到了(i,j)就一定到不了(i-1,j+1)，那么可以dp啦。dp[i][j]表示(i,j)右上角都清了的方案数。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 1050
using namespace std;
long long t,n,m,a[maxn][maxn],dp[maxn][maxn];
int main()
{
    scanf("%lld",&t);
    for (long long i=1;i<=t;i++)
    {
        scanf("%lld%lld",&n,&m);
        for (long long i=1;i<=n;i++)
            for (long long j=1;j<=m;j++)
            {
                scanf("%lld",&a[i][j]);
                dp[i][j]=0;
            }
        for (long long i=1;i<=n;i++)
            for (long long j=m;j>=1;j--)
                dp[i][j]=max(dp[i-1][j+1]+a[i][j],max(dp[i-1][j],dp[i][j+1]));
        printf("%lld
",dp[n][1]);
    }
    return 0;
}