------------------------
A poj 1088
经典水题,裸记忆化搜索
题意:在一个矩阵上,每一个格子有自己的高度,只能从高格子向周围4方向低格子移动,求最长路
分析:
2种思路
1. 进行剪枝,朴素的标记当前位置的最长路,只有当更优时,才进行dfs
实际上,这种算法很容易超时(时限1000ms)
/**********************
*@Name:A - OpenJ_Bailian - 1088
*
*@Author: Nervending
*@Describtion:
*@DateTime: 2018-01-22 15:19:01
***********************/
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e2+;
const int INF=0x3f3f3f3f;
int len[maxn][maxn];
int g[maxn][maxn];
int n,m;
int ans;
const int dir[][]={{,},{-,},{,},{,-}};
void dfs(int nx,int ny,int step){
if(step<=len[nx][ny]) return;
len[nx][ny]=step;
for(int k=;k<;k++){
int x=nx+dir[k][];
int y=ny+dir[k][];
if(g[x][y]<g[nx][ny]&&len[x][y]<step+){
dfs(x,y,step+);
}
}
} int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout); while(~scanf("%d%d",&n,&m)){
int sx,sy;
int mx=-INF;
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
scanf("%d",&g[i][j]);
}
}
memset(len,,sizeof len);
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
dfs(i,j,);
}
}
int ans=-;
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
ans=max(ans,len[i][j]);
}
}
printf("%d\n",ans);
}
return ;
}
2. 转化为DAG最长路问题,记忆化搜索并标记,关键点在于每个点只需要访问1次,时间快了200倍,空间小了4倍
/**********************
*@Name:A - OpenJ_Bailian - 1088
*
*@Author: Nervending
*@Describtion:
*@DateTime: 2018-01-22 15:19:01
***********************/
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e2+;
const int INF=0x3f3f3f3f;
int len[maxn][maxn];
int g[maxn][maxn];
int n,m;
int ans;
const int dir[][]={{,},{-,},{,},{,-}};
int dfs(int nx,int ny){
if(len[nx][ny]) return len[nx][ny];
int mx=;
for(int k=;k<;k++){
int x=nx+dir[k][];
int y=ny+dir[k][];
if(g[x][y]<g[nx][ny]){
mx=max(dfs(x,y)+,mx);
}
}
return len[nx][ny]=mx;
} int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
while(~scanf("%d%d",&n,&m)){
memset(g,0x3f,sizeof g);
memset(len,,sizeof len);
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
scanf("%d",&g[i][j]);
}
}
int ans=;
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
len[i][j]=dfs(i,j);
ans=max(len[i][j],ans);
}
}
printf("%d\n",ans);
}
return ;
}
------------------------
B poj 1579
经典水题,裸记忆化搜索
题意:给出一个递归函数的伪代码:
/**********************
*@Name:
*
*@Author: Nervending
*@Describtion:
*@DateTime: 2018-01-22 22:51:02
***********************/
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e2+;
const int INF=0x3f3f3f3f;
long long dp[maxn][maxn][maxn];
int a,b,c;
long long dfs(int a,int b,int c){
if(a<=||b<=||c<=) return ;
if(a>||b>||c>) return dfs(,,);
if(dp[a][b][c]) return dp[a][b][c];
if(a<b&&b<c) return dp[a][b][c]=dfs(a,b,c-)+dfs(a,b-,c-)-dfs(a,b-,c);
else return dp[a][b][c]=dfs(a-,b,c)+dfs(a-,b-,c)+dfs(a-,b,c-)-dfs(a-,b-,c-);
} int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
memset(dp,,sizeof dp);
while(cin>>a>>b>>c){
if(a==-&&b==-&&c==-){
break;
}
long long ans=dfs(a,b,c);
printf("w(%d, %d, %d) = %lld\n",a,b,c,ans);
} return ;
}
------------------------
C hdu1078
经典水题,裸记忆化搜索,注意读题
题意:一个n*n的正数矩阵,从0,0点出发,每次可以向四个方向跳跃1-k步,要求落点的值大于起点的值,并获得当前点的值,
求权值最大的路
分析:
依然是DAG的记忆化搜索,每个点只访问一次即可,复杂度O(n^2) n==1e2
我写这道题时,一开始没有仔细看题,忽略了起点固定+只能直线(是否停下获取当前权值还是继续走),即使是记忆化搜索,复杂度也飙升到O(n^4*k) n==1e2,k==1e2错了很多发
/**********************
*@Name:
*
*@Author: Nervending
*@Describtion:
*@DateTime: 2018-01-22 23:03:07
***********************/
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e2+;
const int INF=0x3f3f3f3f;
const int dir[][]={,,-,,,,,-};
int g[maxn][maxn];
int dp[maxn][maxn];
#define dx dir[d][1]
#define dy dir[d][0]
#define check(x,y) (x>=1&&y>=1&&x<=n&&y<=n)
int n,k;
int dfs(int nx,int ny){
if(dp[nx][ny]) return dp[nx][ny];
int len=g[nx][ny];
for(int i=;i<=k;i++){
for(int d=;d<;d++){
int x=nx+dx*i;
int y=ny+dy*i;
if(check(x,y)&&g[x][y]>g[nx][ny])
len=max(len,dfs(x,y)+g[nx][ny]);
}
}
return dp[nx][ny]=len;
}
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
while(cin>>n>>k){
if(n==-&&k==-) break;
k=min(n,k);
memset(g,,sizeof g);
memset(dp,,sizeof dp);
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
cin>>g[i][j];
}
}
int ans=dfs(,);
cout<<ans<<endl;
} return ;
}
------------------------
D poj 3280
记忆化搜索/裸的区间DP
题意:给定一个小写字母字符串,可以在字符串任何地方插入和删除字母,每种字母有修改和删除的花费
求让字符串变成回文串的最小花费
分析:
其实是裸的区间DP,但题目时限比较松(2000ms),也可以用DAG上的记忆化搜索解决
对于dp[a][b]表示把a-b变为回文串的最小花费,不断选择是删除/添加Sa还是删除/添加Sb
需要注意的是,在前面删除Sa和在后面添加Sa,结果是一样的,也就是a被匹配了,所以只需要保存删除Sa和添加Sa中较小的一个就行
/**********************
*@Name:
*
*@Author: Nervending
*@Describtion:
*@DateTime: 2018-01-23 01:40:04
***********************/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;
const int maxn=2e3+;
const int INF=0x3f3f3f3f;
int n,m;
char id[maxn];
int cost[maxn];
int dp[maxn][maxn];
int dfs(int a,int b){
if(dp[a][b]!=-) return dp[a][b];
if(a==b) return dp[a][b]=;
int c=(int)id[a];
int d=(int)id[b];
int ans;
if(c==d){
ans=dfs(a+,b-);
}else {
ans=dfs(a+,b)+cost[c];
ans=min(dfs(a,b-)+cost[d],ans);
}
return dp[a][b]=ans;
}
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
while(~scanf("%d%d%s",&n,&m,id)){
memset(dp,-,sizeof dp);
for(int i=;i<n;i++){
char ch[];
int a,b;
scanf("%s%d%d",&ch,&a,&b);;
cost[(int)ch[]]=min(a,b);
}
printf("%d\n",dfs(,m-));
}
return ;
}
若使用区间DP的非递归写法,则可以大幅度优化.
------------------------
E poj 1976
裸01背包
题意:
给一个长为n的数列,选出至多3个连续不相交的字段,要求每个字段的长度不超过m
求选出的字段的最大和
分析:
裸01背包
转化为DAG上的DFS(记忆化搜索)似乎...过不去?,一直是TLE/WA
/**********************
*@Name:
*
*@Author: Nervending
*@Describtion:
*@DateTime: 2018-01-23 03:50:55
***********************/
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+;
const int INF=0x3f3f3f3f;
int num[maxn];
int sum[maxn];
int dp[maxn][];
int n,m;
int dfs(int car,int numh){
if(car>=) return ;
if(dp[car][numh]) return dp[car][numh];
int ans=;
for(int i=numh;i<=n;i++){
ans=max(dfs(car+,i+m)+sum[i+m]-sum[i],ans);
}
return dp[car][numh]=ans;
}
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int casn;
cin>>casn;
while(casn--){
cin>>n;
memset(num,,sizeof num);
memset(dp,,sizeof dp);
memset(sum,,sizeof sum);
for(int i=;i<=n;i++){
scanf("%d",&num[i]);
}
for(int i=;i<=maxn;i++){
sum[i]=sum[i-]+num[i];
}
cin>>m;
cout<<dfs(,)<<endl;
}
return ;
}
改成01背包,即可AC
dp[i][j]表示i个车头在前j个车中最多拉多少乘客,遍历即可
/**********************
*@Name:
*
*@Author: Nervending
*@Describtion:
*@DateTime: 2018-01-23 03:50:55
***********************/
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+;
const int INF=0x3f3f3f3f;
int num[maxn];
int sum[maxn];
int dp[maxn][];
int n,m;
int main(){
//// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int casn;
cin>>casn;
while(casn--){
cin>>n;
memset(num,,sizeof num);
memset(dp,,sizeof dp);
memset(sum,,sizeof sum);
for(int i=;i<=n;i++){
scanf("%d",&num[i]);
}
for(int i=;i<=maxn;i++){
sum[i]=sum[i-]+num[i];
}
cin>>m;
for(int i=;i<=;i++){
for(int j=m;j<=n;j++){
int t=sum[j]-sum[j-m];
dp[j][i]=max(dp[j-][i],dp[j-m][i-]+t);
}
}
cout<<dp[n][]<<endl;
}
return ;
}
------------------------
F poj 2111
裸记忆化搜索
题意;
给一个n*n矩阵,从任一点开始,有一个马,可以向周围"日"走一步,要求输出最长路并还原路径,多解输出字典序最小的一个
分析:
和A题基本一样,不过移动方式改为象棋中马的走法,并增加要求,输出字典序最小的路径,具体做法和最短路的路径还原是一样的,保留前驱节点即可
/**********************
*@Name:
*
*@Author: Nervending
*@Describtion:
*@DateTime: 2018-01-23 12:42:26
***********************/
#include <bits/stdc++.h>
using namespace std;
const int maxn=5e2+;
const int INF=0x3f3f3f3f;
const int dir[][]={,,,-,-,,-,-,,,-,,,-,-,-};
#define dx dir[d][0]
#define dy dir[d][1]
#define check(x,y) (x>=1&&y>=1&&x<=n&&y<=n)
int pre[maxn][maxn][];
int g[maxn][maxn];
int dp[maxn][maxn];
int n;
int dfs(int nx,int ny){
if(dp[nx][ny]) return dp[nx][ny];
int ans=;
int tx=,ty=;
for(int d=;d<;d++){
int x=nx+dx;
int y=ny+dy;
if(check(x,y)&&g[x][y]>g[nx][ny]){
int t=dfs(x,y);
if(ans<t||ans==t&&g[x][y]<g[tx][ty]){
tx=x;
ty=y;
ans=t;
}
}
}
if(ans){
pre[nx][ny][]=tx;
pre[nx][ny][]=ty;
}
return dp[nx][ny]=ans+;
} int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
while(~scanf("%d",&n)){
memset(g,0x3f,sizeof g);
memset(dp,,sizeof dp);
memset(pre,-,sizeof pre);
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
scanf("%d",&g[i][j]);
}
}
int ans=;
int sx=,sy=;
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
int t=dfs(i,j);
if(ans<t||ans==t&&g[sx][sy]>g[i][j]){
ans=t;
sx=i,sy=j;
}
}
}
printf("%d\n",ans);
while(sx!=-){
printf("%d\n",g[sx][sy]);
int t=sx;
sx=pre[sx][sy][];
sy=pre[t][sy][];
}
}
return ;
}
------------------------
G poj 1141
裸的区间dp,难点在于路径还原
题意:
给一个[]()组成的字符串,添加最少的[]()使其匹配,并输出一个最小解答
分析:
首先,如何获得最小花费?
首先如果一个区间的两端可以匹配,则可以转移到[l+1,r-1]这个问题
其次,无论是否匹配,都可以划分为2个子问题 [l][k]和[k+1][r]上
枚举k和外侧匹配进行比较,就可以从之前子问题的解答得到当前问题的最优解了
这时候,其实就可以写出记忆化搜索的代码了
但我们考虑线性的dp过程,
显然,最终答案是从子结构得到的,很容易发现,当前答案一定是从更小的区间得到的
因此我们把DAG分为多层,按区间长度分层
然后就可以很流畅的想到尺取法,递增的枚举区间的长度,并将窗口平移,对窗内进行状态转移即可
其次,如何获得最小解答的字符串
首先 如果对于一个子串,如果是两侧配对最优,
我们可以先输出左括号,再输出[l+1][r-1],再输出右括号
其次,如果两侧匹配的对象是新添加的一个括号,
我们可以在状态转移的时候用一个pos[l][r]保存最优解时区间添加的那个括号是在哪里
打印[l,pos[l][r],pos[l][r]+1,r]
递归的终点就是长度为1的时候,直接输出一对括号即可
/**********************
*@Name:
*
*@Author: Nervending
*@Describtion:
*@DateTime: 2018-01-23 18:49:11
***********************/
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e3+;
const int INF=0x3f3f3f3f;
#define check(x,y) (s[x]=='('&&s[y]==')'||s[x]=='['&&s[y]==']')
int n;
char s[maxn];
int dp[maxn][maxn],pos[maxn][maxn];
void output(int a,int b){
if(a>b) return ;
if(a==b){
if(s[a]=='('||s[a]==')') printf("()");
else printf("[]");
}else{
if(pos[a][b]==-){
putchar(s[a]);
output(a+,b-);
putchar(s[b]);
}else {
output(a,pos[a][b]);
output(pos[a][b]+,b);
}
}
} int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
while(gets(s)){
n=strlen(s);
memset(dp,,sizeof dp);
for(int i=;i<n;i++){
for(int j=,k=i;k<n;j++,k++){
if(check(j,k)){
dp[j][k]=dp[j+][k-]+;
pos[j][k]=-;
}
for(int p=j;p<k;p++){
if(dp[j][p]+dp[p+][k]>=dp[j][k]){
dp[j][k]=dp[j][p]+dp[p+][k];
pos[j][k]=p;
}
}
}
}
output(,n-);
} return ;
}
------------------------
H hdu 2848
博弈转DAG
其实并不是很需要动态规划或者记忆化搜索,是一个DAG状态图上的DFS
这道题是09年多校的一道题,并不出名,提交记录和网络上的题解也很少
我事后查了查,貌似只有代码流传...那个代码也很迷,写的很拖沓
题意:
给一个n和k k<=logn 此处log以10为底,两个人轮流操作,把数字n分为k个段,
每段为xi,然后n=sigma(xi) 并继续操作
如果无法分割为k段,判定为失败,给n和k,问先手的人是否有必胜策略
分析:
大概思路如下,定义dfs(a,b,c) a为还没分割的段落,b为已经分割的段落和,c为段落数量,
初始状态就是dfs(n,0,1),
假设当前为dfs(a,b,c)则可以状态转移到dfs(a/10,b+a%10,2) dfs(a/100,b+a%100,2)....
当c==k时 转移到!dfs(a+b,0,1) 直到结束
这个时间还可以,最大时限是1000ms,如果要优化,可以记忆化,哈希一下即可,但是因为可能的状态空间极大,遍历的重复几率却很低,所以不是很必要
/**********************
*@Name:
*
*@Author: Nervending
*@Describtion:
*@DateTime: 2018-01-24 17:21:28
***********************/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn=1e3+;
const int INF=0x3f3f3f3f;
#define ll long long
ll cmp[maxn];
ll n;
int k;
bool dfs(ll a,ll b,int now){
if(now==&&a<cmp[k-]) return false;
if(now==k)return !dfs(a+b,,);
for(int i=;i<;i++){
if(a<cmp[i]) break;
if(dfs(a/cmp[i],b+a%cmp[i],now+))return true;
}
return false;
} int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout); cmp[]=;
for(int i=;i<=;i++){
cmp[i]=cmp[i-]*;
}
while(~scanf("%lld%d",&n,&k)){
printf("%d\n",dfs(n,,));
}
return ;
}
------------------------
I poj 1191
刘汝佳,算法艺术与信息学竞赛(黑书)p116页的例题,99年noi的一道题
很经典的一个区间dp
中文题+经典题,题意不多赘述,可以直接点上面的题号链接
分析:
经典题,就不分析记忆化搜索的DAG形态再转化到线性dp了
我们先不用题目中的方程,考虑另外一个均方差的方程 E=(sigma(xi)^2)/n-avg^2
可以发现,最优解和sum(i,j,a,b)相关的
可以预处理所有sum(1,1,a,b) 其他子块的可以用简单的容斥定理得到
然后就是dp
怎么从记忆化的DAG搜索转化为线性DP就不在多说,先枚举次数,4重循环枚举块,再枚举横着切/竖着切的位置,即可得到答案
时间复杂度还是很满意的
/**********************
*@Name:
*
*@Author: Nervending
*@Describtion:
*@DateTime: 2018-01-23 21:56:19
***********************/
#include <bits/stdc++.h>
#define rep(x,a,b) for(int x=a;x<b;x++)
using namespace std;
const int maxn=;
const int INF=0x3f3f3f3f;
int g[maxn][maxn];
int n;
int sum[maxn][maxn];
double avg;
int dp[maxn<<][maxn][maxn][maxn][maxn]; int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
while(~scanf("%d",&n)){
memset(sum,,sizeof sum);
avg=;
for(int i=;i<=;i++){
for(int j=;j<=;j++){
scanf("%d",&g[i][j]);
sum[i][j]=sum[i][j-]+sum[i-][j]-sum[i-][j-]+g[i][j];
avg+=g[i][j];
}
}
avg=avg/(double)n;
rep(i,,)
rep(j,,)
rep(k,i,)
rep(p,j,){
int s=sum[k][p]-sum[i-][p]-sum[k][j-]+sum[i-][j-];
dp[][i][j][k][p]=s*s;
}
for(int d=;d<n;d++){
rep(i,,)
rep(j,,)
rep(k,i,)
rep(p,j,){
int t=INF;
rep(a,i,k){
t=min(dp[d-][i][j][a][p]+dp[][a+][j][k][p],t);
t=min(dp[][i][j][a][p]+dp[d-][a+][j][k][p],t);
}
rep(b,j,p){
t=min(dp[d-][i][j][k][b]+dp[][i][b+][k][p],t);
t=min(dp[][i][j][k][b]+dp[d-][i][b+][k][p],t);
}
dp[d][i][j][k][p]=t;
}
}
double ans=dp[n-][][][][];
ans=sqrt(ans/n-avg*avg);
printf("%.3lf\n",ans);
}
return ;
}
有问题欢迎留言