2018多校第九场 HDU 6416 （DP+前缀和优化）

转自：https://blog.csdn.net/CatDsy/article/details/81876341

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define ull unsigned long long

#define mst(a,b) memset((a),(b),sizeof(a))

#define pi acos(-1)

#define pii pair<int,int>

const int INF = 0x3f3f3f3f;

const double eps = 1e-;

const int MAXN = 2e3 + ;

const int MAXM = 2e6 + ;

const ll mod = ;

char s[MAXN][MAXN];

ll tot[MAXN][MAXN], same[MAXN][MAXN];

ll pre_tot[MAXN][MAXN], pre_same[MAXN][MAXN];

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    int t;

    scanf("%d",&t);

    while(t--) {

        int n,m,k;

        scanf("%d%d%d",&n,&m,&k);

        for(int i = ; i <= n; i++)

            scanf("%s",s[i] + );

        for(int i = ; i <= n; i++)

            pre_tot[i][] = pre_same[i][] = ;

        for(int i = ; i <= m; i++) {

            tot[][i] = ;

            pre_tot[][i] = i;

            if(i ==  || s[][i] != s[][i - ]) same[][i] = ;

            else same[][i] = ;

            pre_same[][i] = pre_same[][i - ] + same[][i];

        }

        for(int i = ; i <= n; i++) {

            for(int j = ; j <= m; j++) {

                int l = max(j - k, ), r = min(j + k, m);

                tot[i][j] = (pre_tot[i - ][r] - pre_tot[i - ][l - ] + mod) % mod;

                l = max(j - k + , ), r = min(j + k, m);

                tot[i][j] = (tot[i][j] - (pre_same[i - ][r] - pre_same[i - ][l - ] + mod) % mod + mod) % mod;

                pre_tot[i][j] = (pre_tot[i][j - ] + tot[i][j]) % mod;

                if(j ==  || s[i][j] != s[i][j - ]) same[i][j] = ;

                else {

                    l = max(j - k, ), r = min(j + k - , m);

                    same[i][j] = (pre_tot[i - ][r] - pre_tot[i - ][l - ] + mod) % mod;

                    l = max(j - k + , ), r = min(j + k - , m);

                    same[i][j] = (same[i][j] - (pre_same[i - ][r] - pre_same[i - ][l - ] + mod) % mod + mod) % mod;

                }

                pre_same[i][j] = (pre_same[i][j - ] + same[i][j]) % mod;

            }

        }

        ll ans = ;

        for(int i = ; i <= m; i++)

            ans = (ans + tot[n][i] - same[n][i] + mod) % mod;

        printf("%lld\n",ans);

    }

    return ;

}

题目描述：

给定一个N∗MN∗M的01矩阵

K-seam是满足以下条件的整数序列a：

|a|=n,ai∈[1,m]|a|=n,ai∈[1,m]
|ai−ai+1|≤K,i∈[1,n)|ai−ai+1|≤K,i∈[1,n)

对于第ii行，删除第aiai个数，会得到一个N∗(M−1)N∗(M−1)的矩阵

不同的整数序列可能会得到相同的矩阵

问：可以得到多少种不同的矩阵

题解：

如果无视different的条件
定义状态：dp[i][j]dp[i][j]——删除第 ii 行第 jj 个数可以得到的矩阵总数
可推得转移方程如下：

dp[i][j]=∑x=j−kj+kdp[i−1][x]dp[i][j]=∑x=j−kj+kdp[i−1][x]

在此基础上，加上different的条件
定义状态：

tot[i][j]tot[i][j]——删除第 ii 行第 jj 个数可以得到的不同的矩阵总数
same[i][j]same[i][j]——删除第 ii 行第 jj 个数和删除第 ii 行第 j−1j−1 个数后得到的相同方案数

那么，tot[i][j]tot[i][j]的状态转移方程为：

tot[i][j]=∑x=j−kj+ktot[i−1][x]−∑x=j−k+1j+ksame[i−1][x]tot[i][j]=∑x=j−kj+ktot[i−1][x]−∑x=j−k+1j+ksame[i−1][x]

如果 Matrix[i][j]≠Matrix[i][j−1]Matrix[i][j]≠Matrix[i][j−1] 那么，same[i][j]=0same[i][j]=0
否则，对于第 jj 个和第 j−1j−1 个的转移区间分别为[j−k,j+k][j−k,j+k]，[j−1−k,j−1+k][j−1−k,j−1+k]，那么它们的交叉区间为[j−k,j−1+k][j−k,j−1+k]，即：从该区间内转移得到的方案数会重复计算一次。得到 same[i][j]same[i][j] 的转移方程为：

same[i][j]=∑x=j−kj+k−1tot[i−1][x]−∑x=j−k+1j+k−1same[i−1][x]same[i][j]=∑x=j−kj+k−1tot[i−1][x]−∑x=j−k+1j+k−1same[i−1][x]

时间复杂度为O(n∗m2)O(n∗m2)，对于∑∑做前缀和优化，时间复杂度降为O(n∗m)O(n∗m)

最后，对于第n行计算总的不同的方案数，即ans=∑tot−∑same

巴特西

2018多校第九场 HDU 6416 （DP+前缀和优化）

题目描述：

题解：

最新文章

热门文章