2014-2015 CT S02E10 D题 Coin Table dp

题意：给定一个由"C"和"."构成的n×n图

            给定查询次数m

            每次查询给出r1,c1,r2,c2一个矩形

            求从(1,1)到(n,n)不能走到所给矩形中(只能向右和向下)，问最多可获得多少"C",以及获得这么多"C"的方法数

思路：我们定义一个pair<int,int>dp1[i][j]表示从(1,1)到(i,j)(只能向右和向下)可获得最多的"C"以及方法数,再定义pair<int,int>dp2[i][j]表示从(n,n)到(i,j)(只能向左和向上)可获得最多的"C"以及方法数。预处理完dp1,dp2后，枚举可到达的位置，找到最优解。详见代码：

/*********************************************************
  file name: D.cpp
  author : kereo
  create time:  2015年02月07日 星期六 14时44分49秒
*********************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
const int sigma_size=26;
const int N=100+50;
const int MAXN=1000+50;
const int inf=0x3fffffff;
const double eps=1e-8;
const int mod=1000000000+7;
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define PII pair<int, int>
#define mk(x,y) make_pair((x),(y))
int n,m;
char mp[MAXN][MAXN];
PII dp1[MAXN][MAXN],dp2[MAXN][MAXN]; //pair<int,int>
void DP(PII &now,PII tmp,char c){
    int num=tmp.first+(c == 'C');
    if(num>now.first){
        now.first=num; now.second=tmp.second;
    }
    else if(num == now.first){
        now.second=(now.second+tmp.second)%mod;
    }
}
int main(){
    //freopen("in.txt","r",stdin);
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++)
            scanf("%s",mp[i]+1);
        for(int i=0;i<=n+1;i++)
            for(int j=0;j<=n+1;j++)
                dp1[i][j]=dp2[i][j]=mk(-inf,0);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i == 1 && j == 1){
                    if(mp[i][j] == 'C')
                        dp1[i][j]=mk(1,1);
                    else 
                        dp1[i][j]=mk(0,1);
                }
                else{
                    DP(dp1[i][j],dp1[i-1][j],mp[i][j]);
                    DP(dp1[i][j],dp1[i][j-1],mp[i][j]);
                }
            }
        }
        for(int i=n;i>=1;i--){
            for(int j=n;j>=1;j--){
                if(i == n && j == n){
                    if(mp[i][j] == 'C')
                        dp2[i][j]=mk(1,1);
                    else 
                        dp2[i][j]=mk(0,1);
                }
                else{
                    DP(dp2[i][j],dp2[i+1][j],mp[i][j]);
                    DP(dp2[i][j],dp2[i][j+1],mp[i][j]);
                }
            }
        }
        scanf("%d",&m);
        while(m--){
            int r1,c1,r2,c2;
            scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
            r1++; c1++; r2++; c2++;
            if(r1>r2)
                swap(r1,r2);
            if(c1>c2)
                swap(c1,c2);
            PII ans=mk(0,0),tmp;
            for(int i=r2+1;i<=n;i++){
                tmp.first=dp1[i][c1-1].first+dp2[i][c1].first;
                tmp.second=((ll)dp1[i][c1-1].second*(ll)dp2[i][c1].second)%mod;
                DP(ans,tmp,0);
            }
            for(int j=c2+1;j<=n;j++){
                tmp.first=dp1[r1-1][j].first+dp2[r1][j].first;
                tmp.second=((ll)dp1[r1-1][j].second*(ll)dp2[r1][j].second)%mod;
                DP(ans,tmp,0);
            }
            printf("%d %d\n",ans.first,ans.second);
        }
    }
    return 0;
}

2014-2015 CT S02E10 D题 Coin Table dp

原文：http://blog.csdn.net/u011645923/article/details/43636301