HPU Summer Day 14 自闭场
今天讲了记忆化搜索，拉的题emm真让人自闭啊。
Function Run Fun
Description:
We all love recursion! Don't we?
Consider a three-parameter recursive function w(a, b, c):
if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
1
if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
w(20, 20, 20)
if a < b and b < c, then w(a, b, c) returns:
w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
otherwise it returns:
w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
This is an easy function to implement. The problem is, if implemented directly, for moderate values of a, b and c (for example, a = 15, b = 15, c = 15), the program takes hours to run because of the massive recursion.
Input
The input for your program will be a series of integer triples, one per line, until the end-of-file flag of -1 -1 -1. Using the above technique, you are to calculate w(a, b, c) efficiently and print the result.
Output
Print the value for w(a,b,c) for each triple.
Sample Input
1 1 1
2 2 2
10 4 6
50 50 50
-1 7 18
-1 -1 -1
Sample Output
w(1, 1, 1) = 2
w(2, 2, 2) = 4
w(10, 4, 6) = 523
w(50, 50, 50) = 1048576
w(-1, 7, 18) = 1
Problem solving:
这道题没什么好说的，按照题目上的要求来写一个递归就行了，因为是多组输入，所以要用到记忆化搜索。
Code:
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
ll a,b,c,dp[21][21][21];
ll dfs(ll m,ll t,ll x)
{
if(m<=0||t<=0||x<=0)
return 1;
if(m>20||t>20||x>20)
return dfs(20,20,20);
if(dp[m][t][x]) return dp[m][t][x];
if(m<t&&t<x)
return dp[m][t][x]=dfs(m,t,x-1)+dfs(m,t-1,x-1)-dfs(m,t-1,x);
else
return dp[m][t][x]=dfs(m-1,t,x)+dfs(m-1,t-1,x)+dfs(m-1,t,x-1)-dfs(m-1,t-1,x-1);
}
int main()
{
while(cin>>a>>b>>c)
{
if(a==-1&&b==-1&&c==-1)
break;
printf("w(%lld, %lld, %lld) = %lld\n",a,b,c,dfs(a,b,c));
}
}滑雪
Description:
Glory非常喜欢玩滑滑梯游戏，下面给出了一个n,m的滑道，其中的数字表示滑道的高度。Glory可以从一个点出发向下滑行，每次只能滑行到相邻的位置(上下左右)中高度严格低于当前高度的地方，不能重复划行已经滑行过的地方，但他希望在这个滑道上滑行尽量远的距离，也即是找一条最长的滑道。
Input
第一行输入两个数n,m代表滑梯范围行n和列m(1 <= n,m <= 100)。下面是n行，每行有m个整数，代表高度h，(0<=h<=20000)
Output
输出一个值，代表Glory能够在滑滑梯上面滑行的最长长度是多少
Sample Input
3 3
9 1 2
5 6 7
8 4 3
Sample Output
4
Sample Input
4 7
7 6 5 4 3 2 1
1 5 1 1 1 1 1
1 4 3 1 1 1 1
1 5 6 7 8 1 1
Sample Output
7
hint
样例1：7->6->4->3 长度为4
Problem solving:
四个方向搜索就行了。记忆化搜索要用上，不然会超时。
ma[dx][dy]与ma[x][y]的大小关系判断的时候大于小于都是可以的，这个还是很好理解的吧，降序反过来就是升序。
Code:
#include<iostream>
using namespace std;
int n,m,ma[105][105],dp[105][105];
int d[4][2]={1,0,0,1,0,-1,-1,0};
int dfs(int x,int y)
{
int mid=1;
if(dp[x][y]) return dp[x][y];
for(int i=0;i<4;i++)
{
int dx=x+d[i][0];
int dy=y+d[i][1];
if(dx>=0&&dx<n&&dy>=0&&dy<m&&ma[dx][dy]<ma[x][y])
{
mid=max(mid,dfs(dx,dy)+1);
}
}
return dp[x][y]=mid;
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>ma[i][j];
int ans=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
ans=max(ans,dfs(i,j));
cout<<ans<<endl;
}漫步校园
LL最近沉迷于AC不能自拔，每天寝室、机房两点一线。由于长时间坐在电脑边，缺乏运动。他决定充分利用每次从寝室到机房的时间，在校园里散散步。整个HDU校园呈方形布局，可划分为n*n个小方格，代表各个区域。例如LL居住的18号宿舍位于校园的西北角，即方格(1,1)代表的地方，而机房所在的第三实验楼处于东南端的(n,n)。因有多条路线可以选择，LL希望每次的散步路线都不一样。另外，他考虑从A区域到B区域仅当存在一条从B到机房的路线比任何一条从A到机房的路线更近(否则可能永远都到不了机房了…)。现在他想知道的是，所有满足要求的路线一共有多少条。你能告诉他吗?
Input
每组测试数据的第一行为n(2=<n<=50)，接下来的n行每行有n个数，代表经过每个区域所花的时间t(0<t<=50)(由于寝室与机房均在三楼，故起点与终点也得费时)。
Output
针对每组测试数据，输出总的路线数(小于2^63)。
Sample Input
3
1 2 3
1 2 3
1 2 3
3
1 1 1
1 1 1
1 1 1
Sample Output
1
6
Problem solving:
这道题的题意也太难懂了。。。
让你求最短路的条数，所以我们需要先求出最短路然后再求条数。
先用bfs求出每个点到终点的最短距离然后进行记忆化搜索。
（如果阁下真的是在看我的题解，当你看到这的时候，我衷心的给你道个歉，这道题为了你好还是百度吧
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
struct node{
int x,y,c;
bool friend operator <(node a,node b)
{
return a.c>b.c;
}
}r,w;
ll ma[305][305],vis[305][305],dis[305][305],dp[305][305];
int d[4][2]={0,1,1,0,-1,0,0,-1};
void bfs()
{
priority_queue<node> q;
r.x=n-1,r.y=n-1;r.c=ma[n-1][n-1];
dis[n-1][n-1]=ma[n-1][n-1];
vis[n-1][n-1]=1;
q.push(r);
while(!q.empty())
{
r=q.top();
q.pop();
for(int i=0;i<4;i++)
{
int dx=r.x+d[i][0];
int dy=r.y+d[i][1];
if(dx<0||dy<0||dx>=n||dy>=n||vis[dx][dy]) continue;
w.x=dx,w.y=dy,w.c=r.c+ma[dx][dy];
vis[dx][dy]=1;
q.push(w);
dis[dx][dy]=w.c;
}
}
}
ll dfs(ll x,ll y)
{
if(x==n-1&&y==n-1) return 1;
if(dp[x][y]!=-1) return dp[x][y];
dp[x][y]=0;
for(int i=0;i<4;i++)
{
int dx=x+d[i][0];
int dy=y+d[i][1];
if(dx<0||dy<0||dx>=n||dy>=n||dis[dx][dy]>=dis[x][y]) continue;
dp[x][y]+=dfs(dx,dy);
}
return dp[x][y];
}
int main()
{
while(cin>>n)
{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>ma[i][j];
memset(vis,0,sizeof(vis));
memset(dp,-1,sizeof(dp));
bfs();
cout<<dfs(0,0)<<endl;
}
}Free Candies
Description:
PDF题面:戳我戳我
输入
输出
Problem solving:
题意就是有4个盒子，每个盒子里面都放着糖果，有个最多能放5个糖果的袋子，每次只能取盒子最上面的那个糖果，如果袋子里面有两个颜色相同的糖果可以自己拿走（这道题用数字代表颜色），问你最优情况下能拿走几对糖果，注意是对（2个算一对）。
我们这里可以用一个四维数组表示分别从四堆糖果中取出不同个数的糖果的时候的最优解，用一个now数组代表此时在第i堆数组拿到了第now[i]个糖果，用一个flag数组表示这个颜色的糖果是否在袋子里出现过。然后进行dfs查找，注意这里用到了很多回溯，还有记忆化搜索。可以看一下代码注释了解一下具体的dfs过程。
Code:
#include<bits/stdc++.h>
using namespace std;
int dp[45][45][45][45],n,ma[4][45];
int now[4],flag[45];
int dfs(int x)//x代表的就是当前袋子里放入的糖果个数
{
int ans=0;//初始化为0
if(dp[now[0]][now[1]][now[2]][now[3]]!=-1)//记忆化搜索
return dp[now[0]][now[1]][now[2]][now[3]];
if(x==5) return 0;//袋子里有5个糖果了，不能放入更多，所以return 0
for(int i=0;i<4;i++)//四堆糖果
{
if(now[i]==n) continue;//在这一堆如果已经取到了第n个，即最后一个，就结束这一堆糖果中的查找
int mid=ma[i][now[i]];//代表的是当前取出的糖果的颜色
now[i]++;//下一次要放入的糖果的颜色
if(flag[mid])//如果现在要放入袋子里的糖果的颜色在袋子里已经存在
{
flag[mid]=0;//把袋子里的颜色相同的那个糖果取出来
ans=max(ans,dfs(x-1)+1);//当前的最优值更新一下，dfs(x-1)即取出颜色相同得糖果之后的最优解，加上的1就是取出的糖果和本来准备放进袋子却没放的糖果这一对
flag[mid]=1;//回溯，把从袋子里取出的糖果再放回去
}
else//现在要放入袋子里的糖果的颜色在袋子里不存在
{
flag[mid]=1;//把这个糖果放进去
ans=max(dfs(x+1),ans);//此时袋子里的糖果数加一
flag[mid]=0;//回溯，把放进去的再取出来
}
now[i]--;//回溯，考虑不放这一个糖果的情况
}
return dp[now[0]][now[1]][now[2]][now[3]]=ans;//记忆化
}
int main()
{
while(cin>>n&&n)
{
memset(dp,-1,sizeof(dp));
memset(now,0,sizeof(now));
memset(flag,0,sizeof(flag));
for(int i=0;i<n;i++)
for(int j=0;j<4;j++)
cin>>ma[j][i];
cout<<dfs(0)<<endl;
}
}Zipper
Description:
Given three strings, you are to determine whether the third string can be formed by combining the characters in the first two strings. The first two strings can be mixed arbitrarily, but each must stay in its original order.
For example, consider forming "tcraete" from "cat" and "tree":
String A: cat
String B: tree
String C: tcraete
As you can see, we can form the third string by alternating characters from the two strings. As a second example, consider forming "catrtee" from "cat" and "tree":
String A: cat
String B: tree
String C: catrtee
Finally, notice that it is impossible to form "cttaree" from "cat" and "tree".
Input
The first line of input contains a single positive integer from 1 through 1000. It represents the number of data sets to follow. The processing for each data set is identical. The data sets appear on the following lines, one data set per line.
For each data set, the line of input consists of three strings, separated by a single space. All strings are composed of upper and lower case letters only. The length of the third string is always the sum of the lengths of the first two strings. The first two strings will have lengths between 1 and 200 characters, inclusive.
Output
For each data set, print:
Data set n: yes
if the third string can be formed from the first two, or
Data set n: no
if it cannot. Of course n should be replaced by the data set number. See the sample output below for an example.
Sample Input
3
cat tree tcraete
cat tree catrtee
cat tree cttaree
Sample Output
Data set 1: yes
Data set 2: yes
Data set 3: no
Problem solving:
匹配的时候只会有两种情况
- 第一个字符串当前位置的字符与第三个字符串当前位置的字符相等。
- 第二个字符串当前位置的字符与第三个字符串当前位置的字符相等。
只有这两种情况，所以我们可以直接用dfs进行暴搜。但是这道题需要用到记忆化搜索，用一个二维的标记数组即可。每次查找完当前的一对位置就标记起来，下次遇见的时候就不需要再查找了。
Code:
#include<bits/stdc++.h>
using namespace std;
string a,b,c;
int vis[205][205],flag;
void dfs(int x,int y,int z)
{
if(flag) return ;
if(z==c.size())
{
flag=1;
return ;
}
if(vis[x][y]) return ;
vis[x][y]=1;
if(a[x]==c[z]) dfs(x+1,y,z+1);
if(b[y]==c[z]) dfs(x,y+1,z+1);
}
int main()
{
int n,now=0;
cin>>n;
while(n--)
{
memset(vis,0,sizeof(vis));
flag=0;
cin>>a>>b>>c;
cout<<"Data set "<<++now<<": ";
dfs(0,0,0);
if(flag) puts("yes");
else puts("no");
}
}Bone Collector
Description:
Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave …
The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ?
Input
The first line contain a integer T , the number of cases.
Followed by T cases , each case three lines , the first line contain two integer N , V, (N <= 1000 , V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.
Output
One integer per line representing the maximum of the total value (this number will be less than 2 31).
Sample Input
1
5 10
1 2 3 4 5
5 4 3 2 1
Sample Output
14
Problem solving:
这就是一道背包问题，但是换了描述。
背包问题dp得写法我们还没学，今天学到的是用记忆化搜索解决的背包问题。
具体的解释请看代码注释
Code:
#include<bits/stdc++.h>
using namespace std;
int n,m,a[1050],b[1050],dp[1050][1050];
int dfs(int x,int y)//x代表的是收集到的骨头的个数
{ //y代表的是当前背包剩余容量
if(x==n) return 0;//没有更多骨头可供收集了
if(dp[x][y]) return dp[x][y];//已经搜索过一次了，直接调用
int ans;
if(y<b[x]) ans=dfs(x+1,y);//当前骨头所占体积大于背包所剩体积，放不进去了，直接跳过
else ans=max(dfs(x+1,y),dfs(x+1,y-b[x])+a[x]);//能放进去，要分两种情况，放或不放，取最大值
return dp[x][y]=ans;
}
int main()
{
int t;
cin>>t;
while(t--)
{
memset(dp,0,sizeof(dp));
cin>>n>>m;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++) cin>>b[i];
cout<<dfs(0,m)<<endl;
}
}FatMouse and Cheese
Description:
有一种游戏是的玩法是这样的：
有一个n*n的格子,每个格子有一个数字。
遵循以下规则:
- 玩家每次可以由所在格子向上下左右四个方向进行直线移动，每次移动的距离不得超过m
- 玩家一开始在第一行第一列，并且已经获得该格子的分值
- 玩家获得每一次移动到的格子的分值
- 玩家下一次移动到达的格子的分值要比当前玩家所在的格子的分值要大。
- 游戏所有数字加起来也不大，保证所有数字的和不会超过int型整数的范围
- 玩家仅能在n*n的格子内移动，超出格子边界属于非法操作
- 当玩家不能再次移动时，游戏结束
现在问你，玩家所能获得的最大得分是多少？
Input
有多组测试数据
每组测试样例第一行是两个整数n,m (1≤n≤100)(1≤m≤100),当n和m都是-1时为程序结束标志，直接退出即可
之后n行，每行n个数字，描述n*n的格子里的数字
Output
对于每组测试数据输出一行，这一行仅有一个整数，代表玩家所能获得的最高得分
Sample Input
3 1
1 2 5
10 11 6
12 12 7
-1 -1
Sample Output
37
Problem solving:
这道题跟滑雪那道题差不多，有一点不一样的就是这道题里面每次走的步数可以是不一样的并且范围给了我们。这样的话，仍然暴力搜索就行了。把每种步数都考虑进去可以这样实现
int d[4][2]={0,1,1,0,0,-1,-1,0};
for(int i=0;i<m;i++)
{
for(int j=1;j<=m;j++)
{
int dx=x+d[i][0]*j;
int dy=y+d[i][1]*j;
}
}然后就跟滑雪那道题一样了。
主要要用到记忆化搜索，不然会TLE
Code:
#include<bits/stdc++.h>
using namespace std;
int n,m,ma[105][105],dp[105][105];
int d[4][2]={1,0,0,1,-1,0,0,-1};
int dfs(int x,int y)
{
if(dp[x][y]) return dp[x][y];
int ans=0;
for(int i=0;i<4;i++)
{
for(int j=1;j<=m;j++)
{
int dx=x+d[i][0]*j;
int dy=y+d[i][1]*j;
if(dx>=0&&dy>=0&&dx<n&&dy<n&&ma[dx][dy]>ma[x][y])
{
ans=max(ans,dfs(dx,dy));
}
}
}
return dp[x][y]=ans+ma[x][y];
}
int main()
{
while(cin>>n>>m&&n!=-1&&m!=-1)
{
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>ma[i][j];
cout<<dfs(0,0)<<endl;
}
}
投递腾讯等公司7个岗位
快手一面209人在聊