你是否听说过这个游戏？游戏者在一张特殊的表格中按照规则跳动，使得跳到的数字经过加号和减号的连接，尽可能的逼近零。表格通常是如图 1.1 所示的形状，大小由中间一行的方格数 \(N\) 决定(图 1.1 就是一个 \(N=4\) 的例子)。
游戏者通常是从最下面的方格出发，按照如图 1.2 所示的规则在表格中跳动，当游戏者跳到最顶端的方格时，游戏结束。在游戏未结束前，游戏者不允许跳到表格外。
将游戏者跳到的 \(2?N?1\) 个数字依次写下来，在每两个相邻的数字中间加上加号或减号，使得计算结果最接近零。
例如对于图 1.1 所示的表格，最好的跳动及计算方案是：7+8+(?5)+(?2)?5?1?2=07+8+(?5)+(?2)?5?1?2=0 或 7+10+(?7)?6+(?3)?3+2=07+10+(?7)?6+(?3)?3+2=0 或 7+10+(?5)?10?5+1+2=07+10+(?5)?10?5+1+2=0 或 7+10+(?5)+(?2)?5?3?2=07+10+(?5)+(?2)?5?3?2=0。
输入文件的第一行是 N(N<=50) ，接下来 2?N?1 行给出了表格中每行的每个方格中的数字，第 i+1 行的第 j 个数字对应于表格中第 i 行的第 j 个数字。
文件中第二行的数字表示的是表格顶端的方格中的数字。文件中所有的数字都是整数，同一行相邻的两个数字间用空格符隔开。
输出文件只有一行，是你所求出的最接近零的计算结果的绝对值。
4
2
3 1
-3 5 7
6 10 -2 20
-7 -5 -8
10 8
7
0
这道题我这个奥赛lj一开始并没有想到是一道dp题，当时满脑子只有暴力，dfs巧的是还写炸了，直接暴毙。后来考完试脑子里想的还是我的暴力怎么打挂了。。现在听了题解发现这个dp其实要是想到了很好写，每个状态都是由下一层的状态推上来的，要是想到用一个数组的最后一维来枚举每个状态就可以很容易的把上面的状态转移下来，用一个dp[i][j][k]数组来处理，i表示前i行，j表示第j列，k表示在没有选第i行时可以凑出来的数，dp是一个bool型数组，单纯为了保存前i行是否可以凑出来k这个数，看数据范围，时间效率完全可以接受，所以我们就放心大胆的跑就好了。由于数组的下标不可以是一个负数，所以在初始化的时候都加上一个当前图可以凑出来的最大数，在输出的时候减去这个数就好了，具体实现在代码注释里面写了，这里不解释了，直接看代码。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 35, INF = 0x3f3f3f3f;
bool dp[maxn<<1][maxn][6005];//记得数组不要开小，尹某人害我帮忙调了半个小时代码最后发现数组开小了
int a[maxn<<1][maxn], n, tot;
void Init(){
scanf("%d",&n);
for(int i = 1; i <= n; i++){
int Max = 0;//记录每行的最大值，用来求全图状态的最大值
for(int j = 1; j <= i; j++){
scanf("%d",&a[i][j]);
a[i][j] = abs(a[i][j]);
Max = max(Max, a[i][j]);
}
tot+=Max;
}
for(int i = 1; i < n; i++){//分成两个for循环跑下来，一个for循环有点麻烦（就是懒）
int Max = 0;
for(int j = 1; j <= n-i; j++){
scanf("%d",&a[i+n][j]);
a[i+n][j] = abs(a[i+n][j]);
Max = max(Max, a[i+n][j]);
}
tot += Max;
}
}
int main(){
Init();
dp[2*n-1][1][tot] = 1;//初始化，表示全图可以跑到的最大值tot为true
int now = 0;
for(int i = 2*n - 1; i > n; i--){//从最后一行向上推
for(int j = 1; j <= 2*n-i; j++){//枚举每列
for(int k = 0; k <= 2*tot; k++){//枚举状态
if(dp[i][j][k] == true){//如果在第i行没有选的时候，可以凑出来k这个状态，那么就可以操作
now = k + a[i][j];//加上第（i，j）这个点
dp[i-1][j][now] = dp[i-1][j+1][now]=true;//状态转移
now = k - a[i][j];//减去第（i，j）这个点
dp[i-1][j][now] = dp[i-1][j+1][now]=true;//状态转移
}
}
}
}
for(int i = n; i >= 1; i--){//同上，两种情况分开纯属为了好写，不然还要加判断
for(int j = 1; j <= i;j++){
for(int k = 0; k <= 2*tot; k++){
if(dp[i][j][k]){
now = k + a[i][j];
dp[i-1][j][now] = dp[i-1][j-1][now] = true;
now = k - a[i][j];
dp[i-1][j][now] = dp[i-1][j-1][now] = true;
}
}
}
}
int ans = INF;//把结果初始化成正无穷
for(int i = 0; i <= 2*tot; i++){//每个状态都枚举出来
if(dp[0][0][i]) ans = min(ans, abs(i-tot));//求最大值，（0,0）是因为表示的是在第0行没有选的时候可以凑出来的数，也就是所有状态加上了（1,1）的值之后的状态
}
printf("%d\n",ans);
return 0;
}
谢谢观看，点个关注qwq
原文：https://www.cnblogs.com/hzoi-liujiahui/p/13257182.html