传纸条(共四题) 动态规划 广度搜索 求最大路径 回溯法
这次题目有点多（共有四题），还是逐步变恶心的，我的变量和算法描述可能设置的不规范，请多见谅，还有，请问各位有什么绘制图表的软件吗，有的话劳烦大佬评论一下，word做图表太慢了，不然好多算法我能用图例说明了。
下面是题目要求时限
时间限制: 1600 ms
内存限制: 64 MB
代码长度限制: 16 KB
题目（1）
分析
1.动态规划 传到每一个同学的加权和，与其上方和其左边同学的加权和大小有关。
2.广度优先搜索 这题有点类似走迷宫的题目，通过用广度优先搜索，将 (行数＋列数)相等的值可以算出来（但是这题过于简单，逐行遍历和逐列遍历也可以算出来）
代码
#include <iostream>
using namespace std;
int main()
{
int impression[100][100];//impression用来储存好感度
int group_num, row, col;//group_num用来储存组数，row用来储存行数,col用来储存列数
cin >> group_num;
while(group_num--)
{
cin >> row;
cin >> col;
for(int tmp = 0; tmp < row; tmp++)//通过两次循环输入好感度表
for(int tmp2 = 0; tmp2 < col; tmp2++)
cin >> impression[tmp][tmp2];
for(int tmp = 2; tmp < row; tmp++)//在col为1和row为1的路径上走的时候，只有一条路径
impression[0][tmp] += impression[0][tmp-1];
for(int tmp = 2; tmp < col; tmp++)
impression[tmp][0] += impression[tmp-1][0];
//除了那两条特殊路径之外，其余的(如row为n，col为m)只能从上方(row为n-1,col为m)和左边(row为n,col为m-1)走到
for(int tmp = 1; tmp < row; tmp++)
for(int tmp2 = 1; tmp2 < col; tmp2++)
{
if(impression[tmp - 1][tmp2] > impression[tmp][tmp2 - 1])//找到上方和左边较大的值，然后与好感度表中(m,n)相连
impression[tmp][tmp2] += impression[tmp - 1][tmp2];
else
impression[tmp][tmp2] += impression[tmp][tmp2 - 1];
}
cout << 2*impression[row-1][col-1] <<endl;//找出路径然后乘2
}
return 0;
}
备注:
后面的算法和这个最简单的思路完全不同，如果看后面的题目，请忽略掉以上代码，以免造成误解。但是，那两条特殊边一定要切记，后面题目中特例就有讨论这两条边。
题目（2）
（这题目与上题目不同的地方在于 每个同学至多只能传一次纸条）
分析
刚刚那种算法就行不通了，但是这里我们可以看成两条纸条同时一起走，一条从(1,2)走到(n-1,m)，另一条走到（2,1）走到（n,m-1），只要注意两个的row值不相等，一共走(m+n-3)步的时候，将两个加权步数的总和相加就能得到答案。
代码
#include <iostream>
#include <memory.h>
using namespace std;
int max_int(int a, int b)//输出a,b中的较大者
{
return a>b?a:b;
}
int min_int(int a, int b)//输出a,b中的较小者
{
return a>b?b:a;
}
int num[220][120][120], impression[120][120];//num表示总星数，第一维代表操作步数，第二三行代表去的横坐标，map存储个人星数
int main()
{
int group_num, row, col;//group_num用来储存组数，row用来储存行数,col用来储存列数
cin >> group_num;
while(group_num--)
{
cin >> row;
cin >> col;
//初始化数组num和impression
for(int tmp = 0; tmp <= row+col+2; tmp++)
for(int tmp2 = 0; tmp2 <= row+2; tmp2++)
memset(num[tmp][tmp2],0,sizeof(int)*(row+2));
for(int tmp = 0; tmp < row+2; tmp++)
memset(impression[tmp],0,sizeof(int)*(col+2));
//循环输入好感度表
for(int tmp = 1; tmp <= row; tmp++)
for(int tmp1 = 1; tmp1 <= col; tmp1++)
cin >> impression[tmp][tmp1];
num[1][2][1] = impression[2][1] + impression[1][2];
//某两个点的最大值等于逐步选取上上，上左，左上，左左的较大值，再加上这两个点的好感度
for(int tmp = 1; tmp <= row + col - 3; tmp++)
for(int row1 = 2; row1 <= tmp+1; row1++)
for(int row2 = 1; row2 < row1; row2++)
num[tmp][row1][row2] = max_int( max_int(num[tmp-1][row1][row2],
num[tmp-1][row1-1][row2]), max_int(num[tmp-1][row1][row2-1],
num[tmp-1][row1-1][row2-1]))+impression[row1][tmp+2-row1]+impression[row2][tmp+2-row2];
cout << num[row+col-3][row][row-1] <<endl;
}
return 0;
}
备注：
在这里采取了三位数组 （num[a][row1][row2]） （其中第一维表示操作数，第二维表示第一张纸条的横坐标，第三维表示第二张纸条的横坐标）来表示操作与位置，因为两个纸条相当于同步从(1,2)到(n,m)，所以我们知道，这两张纸条肯定在同一对角线上，坐标可以用 （row1,tmp+2-row1 ）和（row2,tmp+2-row2)来表示。
细心点可以看出，num数组的第二维，我是从1开始循环的，并没有从0开始，是因为我想让数组外面包着一层0，从第一题我们清楚了，有两层特例，但是我们如果要讨论特例过于麻烦，所以在最外层包一层0，还能防止数组越界产生段错误。同理，如果我们要求的是最小加权路径，可以在数组最外层包一层较大值（大于 所给数字最大值 * 操作数即可）
这个算法时间复杂度为Θ（n3）空间复杂度为Θ（n3）。
题目（3）
（这题与上面不同的地方在数组大小变成了1000）
分析
这题按照上面的代码肯定过不去，1000的规模按照Θ（n3）的复杂度来计算肯定超时和超内存，这里我们要想办法尽可能的提升自己算法的速度，减少内存的消耗。
1.关闭流的关联（C和java请无视此条） 在main函数开头加上 std::ios::sync_with_stdio(false); 语句就可以关闭掉同步特效，加速cin的输入。
2.重复使用num数组 在动态规划的时候，数据只和上一次结果有关，这时候就不要浪费，开一个num[2][row1][row2]数组来回倒，用操作数%2来决定是在num的第一维，这样成功将空间复杂度减小为Θ（n2）。（别看是三维数组就以为是Θ（n3）了）
3.在num的第二维遍历的起始点和终止点也做一下判断，不要从1遍历到row完了，多加一个max(2,tmp+2-col)和min(tmp+1,row+1)判断出真实的位置，不要浪费运算时间。
代码
#include <iostream>
#include <memory.h>
using namespace std;
int max_int(int a, int b)
{
return a>b?a:b;
}
int min_int(int a, int b)
{
return a>b?b:a;
}
int num[2][1100][1100], impression[1100][1100];//num表示总星数，第一维代表操作步数，第二三行代表去的横坐标，map存储个人星数
int main()
{
std::ios::sync_with_stdio(false);
int group_num, row, col;
cin >> group_num;
while(group_num--)
{
cin >> row;
cin >> col;
//初始化数组
for(int tmp2 = 0; tmp2 <= row+2; tmp2++)
{
memset(num[0][tmp2],0,sizeof(int)*(row+2));
memset(num[1][tmp2],0,sizeof(int)*(row+2));
}
for(int tmp = 0; tmp < row+2; tmp++)
memset(impression[tmp],0,sizeof(int)*(col+2));
//
for(int tmp = 1; tmp <= row; tmp++)
for(int tmp1 = 1; tmp1 <= col; tmp1++)
cin >> impression[tmp][tmp1];
num[0][2][1] = num[1][2][1] = impression[2][1] + impression[1][2];
for(int tmp = 2; tmp <= row + col - 3; tmp++)
{
int big = min(tmp+1,row+1);
int small = max(2,tmp+2-col);
for(int row1 = small; row1 <= big; row1++)
for(int row2 = small-1; row2 < row1; row2++)
num[tmp%2][row1][row2] = max_int( max_int(num[(tmp-1)%2][row1][row2],
num[(tmp-1)%2][row1-1][row2]), max_int(num[(tmp-1)%2][row1][row2-1],
num[(tmp-1)%2][row1-1][row2-1]))+impression[row1][tmp+2-row1]+impression[row2][tmp+2-row2];
}
cout << num[(row+col+1)%2][row][row-1] <<endl;
}
return 0;
}
备注：
其实有比关闭输入流关联还快的，就是cin.get一次性读入输入数据，然后在给他分配到各个数据中的方式更加快，但是这题对于输入方式没有卡的特别死，这样都能过了就不要自己麻烦自己写分配变量了。
题目（4）
分析
这题要输出路径了，而数组大小变成了与第二题一样的100，因为要路径，所以基于第二题的代码改就好，千万别删成第三题一样的num数组。
这里可以找到规律，每个路径都是从<1,1>,<1,2>…<n-1,m>,<n,m>,<n,m-1>…<2,1><1,1>的，所以我先卡死这七个点的位置。（不卡死这七个点代码会美观点）
由于我们num数组记录了所有操作的最大权值，因此我们考虑采用回溯法。因为num[tmp][row1][row2]是从四个方位中选取最大值与其两个点的好感度值相加而成，所以我们可以反推出四个方位中好感度最大值。
如果存在两个一样的最大值，意味着有两条权值一样的路径，题目要求我们输出字典序，说明从（1,1）开始走的时候权值相同的时候就向右走，说明我们回溯的时候，能向上走向上走，那我们就优先 上上，上左，左上（这里注意两个纸条不能row值相同，不然就传到一个人两次了），左左。
代码
（这里代码有点乱，还没有注释，我后面有空会看看能不能优化的）
#include <iostream>
#include <memory.h>
using namespace std;
int max_int(int a, int b)
{
return a>b?a:b;
}
int min_int(int a, int b)
{
return a>b?b:a;
}
int num[250][120][120], star_map[120][120], answer[2][450];//num表示总星数，第一维代表操作步数，第二三行代表去的横坐标，map存储个人星数
int main()
{
int group_num, row, col;
cin >> group_num;
while(group_num--)
{
cin >> row;
cin >> col;
//初始化数组
for(int tmp = 0; tmp <= row+col+2; tmp++)
for(int tmp2 = 0; tmp2 <= row+2; tmp2++)
memset(num[tmp][tmp2],0,sizeof(int)*(row+2));
for(int tmp = 0; tmp < row+2; tmp++)
memset(star_map[tmp],0,sizeof(int)*(col+2));
//
for(int tmp = 1; tmp <= row; tmp++)
for(int tmp1 = 1; tmp1 <= col; tmp1++)
cin >> star_map[tmp][tmp1];
num[1][2][1] = star_map[2][1] + star_map[1][2];
for(int tmp = 1; tmp <= row + col - 3; tmp++)
{
int big = min(tmp+1,row+1);
int small = max(2,tmp+2-col);
for(int row1 = small; row1 <= big; row1++)
for(int row2 = small-1; row2 < row1; row2++)
num[tmp][row1][row2] = max_int( max_int(num[tmp-1][row1][row2],
num[tmp-1][row1-1][row2]), max_int(num[tmp-1][row1][row2-1],
num[tmp-1][row1-1][row2-1]))+star_map[row1][tmp+2-row1]+star_map[row2][tmp+2-row2];
}
answer[0][0] = answer[1][0] = answer[0][2*(col+row)-4] = answer[1][2*(col+row)-4] =
answer[0][1] = answer[1][2*(col+row)-5]= 1;
answer[0][col+row-2] = answer[0][col+row-1] = row, answer[1][col+row-2] = answer[1][col+row-3] = col;
answer[0][col+row-3] = row - 1, answer[1][col+row-1] = col - 1;
answer[0][2*(col+row)-5] = answer[1][1] = 2;
int num1 = row - 1, num2 = row, num3 = col, num4 = col - 1, tmp_num, tmp_numa;
for(int tmp = row + col - 3; tmp > 1; tmp--)
{
tmp_numa = row + col - 2 - tmp;
tmp_num = num[tmp][num2][num1] - star_map[num1][num3] - star_map[num2][num4];
if(tmp_num == num[tmp-1][num2 - 1][num1 - 1])
{
num1--;
num2--;
}
else if(tmp_num == num[tmp-1][num2 - 1][num1])
{
num2--;
num3--;
}
else if(tmp_num == num[tmp-1][num2][num1 - 1] && num2 != num1)
{
num1--;
num4--;
}
else if(tmp_num == num[tmp-1][num2][num1])
{
num3--;
num4--;
}
answer[0][col+row-3 - tmp_numa] = num1;
answer[1][col+row-3 - tmp_numa] = num3;
answer[0][col+row-1 + tmp_numa] = num2;
answer[1][col+row-1 + tmp_numa] = num4;
}
cout << num[row+col-3][row][row-1] <<endl;
for(int tmp = 0; tmp < 2*(row+col)-4; tmp++)
cout << "<" << answer[0][tmp] << "," << answer[1][tmp]<< "> ";
cout << "<1,1>"<<endl;
}
return 0;
}
分析：
那七个固定点应该是可以融合进函数里面几个，但是时间不够没来得及测试，中间那段四个if连用是判断四个方位，下面四行对answer的操作是为了保存两个纸条的操作，然后进过迭代直到回到(1,2)与(2,1) 。
吐槽
小渊，小轩，你们两个给我出去。1000*1000个同学你两都要传纸条。