Problem 1032 Pixel Picture（foj内网）（dp）

201707 （ACM）动态规划

题解

• dp
• 注意43行有无加一的区别

代码

#include<cstdio>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)a.size()
const int N=105;
const ll mod=1e9+7;
ll f[N][N][N][2][2];
ll s[N][N][N][2][2];
ll C[N][N];
ll calc(int i,int x1,int y1,int x2,int y2,int t1,int t2) {
    return (s[i-1][x2][y2][t1][t2]+s[i-1][x1-1][y1-1][t1][t2]-s[i-1][x1-1][y2][t1][t2]-s[i-1][x2][y1-1][t1][t2])%mod;
}
void upd(ll &a, ll b){
    a+=b;
    a%=mod;
}
int main() {
    int n,m;
    while(~scanf("%d%d",&n,&m)) {
        ///init
        memset(f,0,sizeof(f));
        memset(s,0,sizeof(s));
        ///solve
        for(int i=1;i<=n;++i) {
            rep(l,1,m+1) {
                rep(r,l,m+1) {
                    f[i][l][r][0][0]=(calc(i,l,l,r,r,0,0)+1)%mod;
                    f[i][l][r][0][1]=(calc(i,l,r+1,r,m,0,0)+calc(i,l,r,r,m,0,1))%mod;
                    f[i][l][r][1][0]=(calc(i,1,l,l-1,r,0,0)+calc(i,1,l,l,r,1,0))%mod;
                    f[i][l][r][1][1]=(calc(i,1,r+1,l-1,m,0,0)+calc(i,1,r,l-1,m,0,1)+calc(i,1,r+1,l,m,1,0)+calc(i,1,r,l,m,1,1))%mod;
                }
            }
            rep(l,1,m+1) {
                rep(r,1,m+1) {
                    rep(a,0,2) rep(b,0,2) s[i][l][r][a][b]=(s[i][l-1][r][a][b]+s[i][l][r-1][a][b]-s[i][l-1][r-1][a][b]+f[i][l][r][a][b])%mod;
                }
            }
        }
        ///print
        ll ans=0;
        rep(i,1,n+1) {
            rep(a,0,2) rep(b,0,2) upd(ans,s[i][m][m][a][b]);
        }
        ans=(ans+mod)%mod;
        cout<<ans<<endl;
    }
    return 0;
}

Problem 1032 Pixel Picture
Accept: 4 Submit: 4
Time Limit: 5000 mSec Memory Limit : 131072 KB
Problem Description

小茗同学最近沉迷于像素画风的游戏中，他想尝试自己设计新的像素角色，他需要在一个n * m大小的画布上填充单元格。为了简化问题，背景色为白色，小茗同学填充色为黑色。

小茗同学也并没有想好新的角色长什么样，所以他想知道在n * m的画布上能画多少种图像出来。但是这样的数量太多了，小茗同学提出了两点限制：

1. 图像必须是联通的，也就是任意两个黑色的单元格可以通过其他的黑色格子相互到达。

2. 在坐标(x1, y1)的黑色单元格到(x2, y2)的黑色单元格的最短距离为|x1-x2|+|y1-y2|。

由于种类数太多，所以方案数对1000000007(1e9 + 7)取模。
Input

包含多组测试数据。

每组测试数据包含两个数n,m，表示图画大小1 <= n, m <= 100。
Output

每组测试数据输出一个数表示对应的方案数，对1000000007(1e9 + 7)取模。
Sample Input
2 2
3 4
Sample Output
13
571
Hint

2x2的方案：
10|01|00|00|11|00|10|01|11|11|10|01|11
00|00|10|01|00|11|10|01|10|01|11|11|11
Source
2017暑期选拔赛第一场