动态规划-java语言练习一：暴力DP

重新进行算法的一个卷，主要复习高二学的动态规划知识（

练习题目参考洛谷提单：【动态规划】普及~省选的DP题 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

练习暴力DP主要是先找回DP的感觉，练习推转移方程。

T1. 乌龟棋 线性DP

[P1541 NOIP2010 提高组] 乌龟棋 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目讲从起点到终点，每个点有不同的分数，有指定数量的1,2,3,4号牌，每张最多用一次，用几号牌乌龟就走几格。求能获得的最高分数。

设num[i]为i处的分数，count[i]为某号牌的张数。

分状态

可以看出状态可以由使用不同种牌的次数来划分，因此设s[a][b][c][d]为使用了a张1号，b张2号...牌能取得的最高分数。

显然，s[0][0][0][0]=num[1]，我们要求的就是s[num_a][num_b]...的值。

转移方程

对于某种牌，只有使用和不使用两种选择。因此，对于1号牌：

$$s[a][b][c][d] = max (s[a-1][b][c][d]+num[r],s[a][b][c][d])$$

其中，$$r=1+a+2_b+3_c+4*d$$。（注意起点编号是1，所以r要先+1）

同理，可推得总的状态转移方程：

$$s[a][b][c][d]=max(s[a-1][b][c][d],s[a][b-1][c][d],s[a][b][c-1][d],s[a][b][c][d-1])+ num[r]$$

即某状态可以由少使用一张某种牌+这个状态对应的地图上的点的分数来得到。

当然，由于输入说可能没有某种牌(a=0,b=0,...)，代码实现的时候我们只能把这四种牌的转移方程拆开写。

代码

import java.util.Scanner;
public class 乌龟棋1541 {
    public static void main(String[] args){
        int n,m;
        int[] num = new int[400];
        int[] count = {0,0,0,0,0};
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i = 1;i<=n;i++) num[i] = sc.nextInt();
        for(int i = 1;i<=m;i++) count[sc.nextInt()]++;
        int[][][][] s= new int[41][41][41][41];
        s[0][0][0][0] = num[1];
        for(int i = 0;i<=count[1];i++){
            for(int j = 0;j<=count[2];j++){
                for(int k = 0;k<=count[3];k++){
                    for(int l = 0;l<=count[4];l++){
                        int r = 1+i+j*2+k*3+l*4;
                        if(i!=0) s[i][j][k][l] = Math.max(s[i][j][k][l],s[i-1][j][k][l]+num[r]);
                        if(j!=0) s[i][j][k][l] = Math.max(s[i][j][k][l],s[i][j-1][k][l]+num[r]);
                        if(k!=0) s[i][j][k][l] = Math.max(s[i][j][k][l],s[i][j][k-1][l]+num[r]);
                        if(l!=0) s[i][j][k][l] = Math.max(s[i][j][k][l],s[i][j][k][l-1]+num[r]);
                    }
                }
            }
        }
        System.out.println(s[count[1]][count[2]][count[3]][count[4]]);
    }
}

T2. 樱花 多重背包

P1833 樱花 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)