欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

计蒜客T31434 广场车神(二维前缀和优化dp)

程序员文章站 2022-06-28 18:31:24
题目链接Reference:https://www.cnblogs.com/dilthey/p/9757781.html首先容易想到的常规dp是,初始化dp(i,j)=0dp(i,j)=0dp(i,j)=0,对于当前下标(i,j)(i,j)(i,j)为右上角的一个边长为k+1k+1k+1的正方形内:dp(i,j)=∑x=i−ki∑y=j−kjdp(x,y)dp(i,j)= \sum_{x=i-k}^{i} \sum_{y=j-k}^{j}dp(x,y)dp(i,j)=∑x=i−ki​∑y=j−kj​...

题目链接


Reference:https://www.cnblogs.com/dilthey/p/9757781.html

首先容易想到的常规dp是,初始化dp(i,j)=0dp(i,j)=0,对于当前下标(i,j)(i,j)为右上角的一个边长为k+1k+1的正方形内:

dp(i,j)=x=ikiy=jkjdp(x,y)dp(i,j)= \sum_{x=i-k}^{i} \sum_{y=j-k}^{j}dp(x,y)

但是这样的时间复杂度为O(nwk2)O(nwk^2),使用二维前缀和优化

设最后dp方程的二维前缀和sum(i,j)=x=1iy=1jdp(x,y)sum(i,j)= \sum_{x=1}^{i} \sum_{y=1}^{j}dp(x,y),因为当前状态只能从一个(k+1)(k+1)(k+1)*(k+1)的正方形内的状态转移,如果使用二维前缀和计算这一方形区域,设下边界为d=ik1d=i-k-1,左边界为l=jk1l=j-k-1,状态转移方程为:

dp(i,j)=(sum(i1,j)+sum(i,j1)sum(i1,j1))(sum(d,j)+sum(i,l)sum(d,l))dp(i,j)=(sum(i-1,j)+sum(i,j-1)−sum(i-1,j-1))−(sum(d,j)+sum(i,l)−sum(d,l)),画个图很容易看出来,然后根据二维前缀和的定义:

sum(i,j)=(sum(i1,j)+sum(i,j1)sum(i1,j1))+dp(i,j)=2(sum(i1,j)+sum((i,j1)sum(i1,j1))(sum(d,j)+sum(i,l)sum(d,l))sum(i,j)=(sum(i-1,j)+sum(i,j-1)−sum(i-1,j-1))+dp(i,j)=2(sum(i-1,j)+sum((i,j-1)−sum(i-1,j-1))−(sum(d,j)+sum(i,l)−sum(d,l))

那么最后的答案就是:

dp(n,m)=sum(n,m)(sum(n1,m)+sum(n,m1)sum(n1,m1))dp(n,m)=sum(n,m)−(sum(n-1,m)+sum(n,m-1)−sum(n-1,m-1))

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <bitset>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define Vector Point
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const double dinf=1e300;
const ll INF=1e18;
const int Mod=998244353;
const int maxn=2e5+10;

ll sum[2020][2020];

int main(){
    freopen("racing.in","r",stdin);
    freopen("racing.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,m,k;
    cin>>n>>m>>k;
    sum[1][1]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            if(i==1 && j==1) continue;
            int l=max(0,i-k-1),d=max(0,j-k-1);
            sum[i][j]=(2*(sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1])%Mod-(sum[l][j]+sum[i][d]-sum[l][d])%Mod+Mod)%Mod;
        }
    ll ans=(sum[n][m]-(sum[n-1][m]+sum[n][m-1]-sum[n-1][m-1])%Mod+Mod)%Mod;
    cout<<ans<<endl;
    return 0;
}

本文地址:https://blog.csdn.net/qq_44691917/article/details/107441455

相关标签: 计蒜客