2019ICPC南京现场赛 C-digit path 拓扑dp

说来惭愧，A题卡了4个小时我都不信，都最后铜也没拿上。。

题意：

找长度大于等于4的 严格递增差1 的 能在扩增的 路线有多少条。

题目思路：

严格递增差一，很容易想到，有向无环图(DAG)

我们在DAG上进行拓扑DP就可以乐，因为拓扑满足无后效性

所以，我们直接找出状态转移方程：

            dp[e][2]=(dp[e][2]+dp[u][1])%mod;
            dp[e][3]=(dp[e][3]+dp[u][2])%mod;
            dp[e][4]=(dp[e][4]+dp[u][3]+dp[u][4])%mod;

然后 入度为0的点 dp[i][1]=1；

上述转移方程的意思是：到达该点长度为3的+等于前一个点到达长度为2的数量，特别的，到达该点大于等于4的+等于到达前一个长度为3的与到达前一个点长度大于等于4的。

然后就过了...

说来很伤心..明年去南京复仇叭...加油！

不负领导，不负队友！

AC:

#pragma GCC optimize(2)
#include<bits/stdc++.h>
typedef long long ll;
const int maxn=1e6+5;
using namespace std;
ll n,m;
int mp[1005][1005];
ll dp[maxn][6];
int pos[1005][1005];
int in[maxn],out[maxn];
struct node{
    int e,next;
}edge[maxn*4];
int head[maxn*4];
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
ll cnt=0;
void addedge(int u,int v)
{
    edge[cnt]=node{v,head[u]};
    head[u]=cnt++;
}
void Torder()
{
    queue<int>q;
    for(int i=1;i<=n*m;i++)
    {
        if(!in[i])
        {
            q.push(i);
            dp[i][1]=1;
        }
    }
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];~i;i=edge[i].next)
        {
            int e=edge[i].e;
            in[e]--;
            dp[e][2]=(dp[e][2]+dp[u][1])%mod;
            dp[e][3]=(dp[e][3]+dp[u][2])%mod;
            dp[e][4]=(dp[e][4]+dp[u][3]+dp[u][4])%mod;
            if(!in[e]) q.push(e);
        }
    }
}
int main()
{
    int cot=0;
    memset(dp,0,sizeof(dp));
    memset(head,-1,sizeof(head));
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
        for(int k=1;k<=m;k++)
        {
            scanf("%lld",&mp[i][k]);
            pos[i][k]=++cot;
        }
    for(int i=1;i<=n;i++)
    {
        for(int k=1;k<=m;k++)
        {
            for(int j=0;j<4;j++)
            {
                int mx=i+dx[j],my=k+dy[j];
                if(mp[i][k]+1==mp[mx][my]&&mx>=1&&my>=1&&mx<=n&&my<=m)
                {
                    addedge(pos[i][k],pos[mx][my]);
                    in[pos[mx][my]]++;
                    out[pos[i][k]]++;
                }
            }
        }
    }
    Torder();
    ll res=0;
    for(int i=1;i<=n*m;i++)
    {
        if(!out[i])
        {
            res+=dp[i][4];
            res%=mod;
        }
    }
    printf("%lld\n",res);
    return 0;
}

/**

**/