首页 > 其他 > 详细

luoguP1373 小a和uim之大逃离

时间:2019-04-25 22:39:59      阅读:145      评论:0      收藏:0      [点我收藏+]

DP专题

题目链接

思路
\(f[i][j][a][b][0/1]\)表示在\((i,j)\)这个格子,小a有a滴魔液,他的伙伴有b滴,上一步是小a(0)或者他的伙伴(1)吸取的魔液。
(显然)数组开不下

#include<iostream>
#include<cstring>
#include<cstdio>
#define LL long long
using namespace std;
const LL mod = 1000000007;
int n,m,k;
int val[805][805],f[105][105][5][5][2];
LL ans;
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
      scanf("%d",&val[i][j]);
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
      f[i][j][val[i][j]][0][0]=1;
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
     {
        for(int a=0;a<=k;a++)
         for(int b=0;b<=k;b++)
         {
            f[i][j][a][b][0]+=f[i][j-1][a-val[i][j]][b][1];
            f[i][j][a][b][0]+=f[i-1][j][a-val[i][j]][b][1];
            f[i][j][a][b][0]%=mod;
            f[i][j][a][b][1]+=f[i][j-1][a][b-val[i][j]][0];
            f[i][j][a][b][1]+=f[i-1][j][a][b-val[i][j]][0];
            f[i][j][a][b][1]%=mod;
        //  cout<<f[i][j][a][b][0]<<"*"<<f[i][j][a][b][1]<<endl;
         }
     }
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
      for(int a=0;a<=k;a++)
       ans=(ans+(LL)f[i][j][k][k][1])%mod; 
    printf("%lld\n",ans);
    return 0;
}

窃取题解的思路

\(f[i][j][h][0/1]\) \(h\)表示小a与他的伙伴的魔液的差值。

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;
const int inf=1<<26;
int dp[805][805][20][2];
int n,m,k;
int a[802][805];
const int mod=(int)1e9+7;
int main()
{
    scanf("%d%d%d",&n,&m,&k);++k;
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
      scanf("%d",&a[i][j]),
      dp[i][j][a[i][j]%k][0]=1;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            for(int h=0;h<=k;h++)
            {
                dp[i][j][h][0]=(dp[i][j][h][0]+dp[i-1][j][(h-a[i][j]+k)%k][1])%mod;
                dp[i][j][h][0]=(dp[i][j][h][0]+dp[i][j-1][(h-a[i][j]+k)%k][1])%mod;
                dp[i][j][h][1]=(dp[i][j][h][1]+dp[i][j-1][(h+a[i][j])%k][0])%mod;
                dp[i][j][h][1]=(dp[i][j][h][1]+dp[i-1][j][(h+a[i][j])%k][0])%mod;
            }
        }
    }
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
      ans=(ans+dp[i][j][0][1])%mod;
    printf("%d\n",ans);
    return 0;
}

luoguP1373 小a和uim之大逃离

原文:https://www.cnblogs.com/karryW/p/10771515.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!