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

***

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

练习题目参考洛谷提单：[【动态规划】普及\~省选的DP题 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/training/1435#information)

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

## T1. 乌龟棋 线性DP

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

题目讲从起点到终点，每个点有不同的分数，有指定数量的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,...)，代码实现的时候我们只能把这四种牌的转移方程拆开写。

### 代码

```java
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)](https://www.luogu.com.cn/problem/P1833)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blog.mcyou.cc/suan-fa-xiang-guan/suan-fa/dong-tai-gui-hua-java-yu-yan-lian-xi-yi-bao-li-dp.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.