P3974 [TJOI2015]组合数学

佚名 6年前 (2019-04-17) 随笔 559人围观抢沙发百度已收录

题目链接

题意分析

结论题 + \(DP\)

我们可以将从左上到右下走看成一个\(DAG\)

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

那么就是要我们求当前\(DAG\)的最小覆盖

首先 \(D\)氏定理

一个\(DAG\)的最小覆盖就是这个\(DAG\)的最大独立集

然后就是\(DP\)求最大独立集

根据这个方格

最大独立集中任意两个元素都是满足左下-右上结构的

所以我们用\(dp\)就可以了

\(dp_{i,j}\)表示以\((i,j)\)为左下角 \((1,m)\)为右上角的最大独立集

那么转移时就是

\(dp_{i,j}=max(dp_{i-1,j+1}+a_{i,j},max(dp_{i-1,j},dp_{i,j+1}))\)

CODE:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<list>
#include<set>
#include<deque>
#include<vector>
#include<ctime>
#define ll long long
#define inf 0x7fffffff
#define N 1088
#define IL inline
#define M 1008611
#define D double
#define ull unsigned long long
#define R register
using namespace std;
template<typename T>IL void read(T &_)
{
    T __=0,___=1;char ____=getchar();
    while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();}
    while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();}
    _=___ ? __:-__;
}
/*-------------OI使我快乐-------------*/
int T,n,m;
int num[N][N];
ll dp[N][N];
int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    read(T);
    while(T--)
    {
        read(n);read(m);
        memset(dp,0,sizeof dp);
        for(R int i=1;i<=n;++i)
         for(R int j=1;j<=m;++j)
          read(num[i][j]);
        for(R int i=1;i<=n;++i)
         for(R int j=m;j;--j)
          dp[i][j]=max(dp[i-1][j+1]+num[i][j],max(dp[i-1][j],dp[i][j+1]));
        printf("%lld\n",dp[n][1]);    
    }
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}