51nod 1084 矩阵取数问题 V2

Type:DP,多路(进程)DP

题目

一个M*N矩阵中有不同的正整数,经过这个格子,就能获得相应价值的奖励,先从左上走到右下,再从右下走到左上。第1遍时只能向下和向右走,第2遍时只能向上和向左走。两次如果经过同一个格子,则该格子的奖励只计算一次,求能够获得的最大价值。

例如:3 * 3的方格。

1 3 3
2 1 3
2 2 1

能够获得的最大价值为:17。1 -> 3 -> 3 -> 3 -> 1 -> 2 -> 2 -> 2 -> 1。其中起点和终点的奖励只计算1次。

Input

第1行:2个数M N,中间用空格分隔,为矩阵的大小。(2 <= M, N <= 200)
第2 – N + 1行:每行M个数,中间用空格隔开,对应格子中奖励的价值。(1 <= A[i,j] <= 10000)

Output

输出能够获得的最大价值。

Input示例

3 3
1 3 3
2 1 3
2 2 1

Output示例

17

题解

一开始的想法是先走一遍取最大值,然后回溯到起点,把走过的地方置为 0,然后WA= =,发现是行不通的,因为两次都是最有没办法保证全局最优.

然后搜了题解

这里用到多进程dp,即我们用 dp[step][j][k] 代表当前走了 step 步,第一个走的人在第 j行,第二个走的人在第 k行时最大的经过路径之和.

如果 j==k 时,即两个人当前路径点重合了.我们只需要随便选取一个加到记忆化数组中即可.

而当我们多路dp时,两个人来到当前状态的方向可能是

(1) 第一个人往下走,第二个人往下走
(2) 第一个人往下走,第二个人往右走
(3) 第一个人往右走,第二个人往下走
(4) 第一个人往右走,第二个人往右走

我们只需要在遍历到每个状态时,对以上四个状态找最大值加上两个人当前地点的数字即可

答案是dp[M+N][N][N]

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=210;
int N,M,A;
int mp[maxn][maxn],dp[2*maxn][maxn][maxn];

int main(){
    ///读题bug,N是行,第二个读入
    scanf("%d%d",&M,&N);
    for(int i=1;i<=N;++i){
        for(int j=1;j<=M;++j){
            scanf("%d",&mp[i][j]);
        }
    }
    ///枚举步数
    for(int i=2;i<=N+M;++i){
        ///枚举位于行数 i-j or k即为当前所处列(因为总步数为i(行数加列数和))
        for(int j=1;j<=N&&i-j>=0;++j){
            for(int k=1;k<=N&&i-k>=0;++k){
                ///分为四种情况,下下,下右,右下,右右
                if(k==j){
                    //下下
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k-1]+mp[j][i-j]);
                    //下右
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k-1]+mp[j][i-j]);
                    //右下
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k]+mp[j][i-j]);
                    //右右
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k]+mp[j][i-j]);
                }else{
                    //下下
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k-1]+mp[j][i-j]+mp[k][i-k]);
                    //下右
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k-1]+mp[j][i-j]+mp[k][i-k]);
                    //右下
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k]+mp[j][i-j]+mp[k][i-k]);
                    //右右
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k]+mp[j][i-j]+mp[k][i-k]);
                }
            }
        }
    }
    printf("%d\n",dp[N+M][N][N]);
    return 0;
}


51nod 1020 逆序排列

Type:DP,逆序数

题目

在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
如2 4 3 1中,2 1,4 3,4 1,3 1是逆序,逆序数是4。

1-n的全排列中,逆序数最小为0(正序),最大为n*(n-1) / 2(倒序)
给出2个数n和k,求1-n的全排列中,逆序数为k的排列有多少种?
例如:n = 4 k = 3。

1 2 3 4的排列中逆序为3的共有6个,分别是:
1 4 3 2
2 3 4 1
2 4 1 3
3 1 4 2
3 2 1 4
4 1 2 3

由于逆序排列的数量非常大,因此只需计算并输出该数 Mod 10^9 + 7的结果就可以了。

Input

第1行:一个数T,表示后面用作输入测试的数的数量。(1 <= T <= 10000)
第2 – T + 1行:每行2个数n,k。中间用空格分隔。(2 <= n <= 1000, 0 <= k <= 20000)

Output

共T行,对应逆序排列的数量 Mod (10^9 + 7)

Input示例

1
4 3

Output示例

6

题解

考虑 dp[i][j] 表示 元素个数为 i 个时 逆序数为 j 的全排列个数为 dp[i][j] 个.

设当前元素为 N ,则 N 可以放在原来 N-1 个元素的任意全排列的 N-i(i∈[0,N)) 上的位置.

当 N 放在位置 N-i 上时,该排列的逆序数会增长 i (因为N最大,所以后面i个为逆序,前面为顺序),所以当我们想要找长度为 N ,逆序数为 k 的个数时,只需要找长度为 N-1 ,逆序数为 k-i 的全排列的个数即可.

所以 dp[N][k] = lambda(dp[N-1][k-i] | i∈[0,N))

复杂度为 O(k(N^2)) 会炸.

考虑优化:

① dp[N][k] = lambda(dp[N-1][k-i] | i∈[0,N))
② dp[N][k-1] = lambda(dp[N-1][k-1-i] | i∈[0,N))
①-②: dp[N][k]-dp[N][k-1] = dp[N-1][k]-dp[N-1][k-N]
dp[N][k]=dp[N-1][k]-dp[N-1][k-N]+dp[N][k-1]

得出递推公式:

① dp[i][j]=1 j=0
② dp[i][j]=dp[i-1][j]-dp[i-1][j-i]+dp[i][j-1]

由题目的约束条件:

逆序数最小为0(正序),最大为n*(n-1) / 2(倒序)

故枚举逆序数只需要枚举到 i*(i-1)/2&&j\<20000即可
注意j-i不能<0

Code

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int dp[1010][20010];

void init(){
    for(int i=1;i<=1000;++i) dp[i][0]=1;
    for(int i=2;i<=1000;++i){
        for(int j=1;j<=i*(i-1)/2&&j<=20000;++j){
            dp[i][j]=(dp[i][j-1]+dp[i-1][j])%mod;
            if(j-i>=0)dp[i][j]=(((dp[i][j]-dp[i-1][j-i])%mod)+mod)%mod;
        }
    }
}

int main(){
    init();
    int T;
    scanf("%d",&T);
    while(T--){
        int n,k;
        scanf("%d%d",&n,&k);
        printf("%d\n",dp[n][k]);
    }
    return 0;
}