重新进行算法的一个卷，主要复习高二学的动态规划知识（
练习题目参考洛谷提单：【动态规划】普及~省选的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)
