首页 > 代码库 > Codeforces 132C. Vasya and Beautiful Arrays【DP,dfs】
Codeforces 132C. Vasya and Beautiful Arrays【DP,dfs】
题目大意:
在一根数轴上有一只机器龟,它能够听从人们给它的指令做出向前走一步(F)和向后转(T)的操作。给出初始操作,你最开始有修改n步指令的权利(每一个指令可以被修改很多次),问在你修改n次之后,海龟离原点的最大距离。
做法:
很直观的想法,尽可能的将T转化为F,也算是一种贪心的做法吧。
我们用dfs(i,j,t,cur),其中i表示当前遍历的命令的序号,j表示从0~i过程中我转换了多少个T,t表示从0~i的序号中总共出现了多少次T,cur表示当前相对于原点的距离(有正有负),dp[i][dre][j][cur],其中i表示当前遍历的命令的序号,dre表示当前状态乌龟是往左还是往右(初始往右),j表示当前状态还剩多少次操作,cur表示当前状态相对于原点的距离。在dp数组中,由于这四个值确定的话,那么继续搜下去我们得到的结果是一定的,所以可以以此进行记忆化搜索。
其实前面还遗留了一个问题,我们贪心的尽可能的将T转化为F,那么一定会出现T的数目小于操作数的情况。如果遇到这样的情况,我们可以算一下还剩下多少的操作数没有转。因为每步指令可以被修改很多次,那么如果剩下的是偶数,那对结果是没有影响的,如果是奇数,那我们只好将最左边或者最右边的F改为T了(最后算出来的距离减一)。
动态规划的题,一般都有两种写法,一种是直推(for循环),另一种就是写递归函数(dfs),用dp数组实现记忆化搜索。最开始拿到这题的时候呢,我首先想的还是直推,
后来写得有点问题,换成了dfs的写法,利用一个四维数组进行记忆化搜索.
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #define N 51 using namespace std; int dp[N*2][2][N][N*4]; char a[N*2]; int n,len,ans; int dfs(int idx,int j,int t,int cur) { if(j>n) return 0; if(idx==len) { ans=max(ans,abs(cur)-((n-j)&1));//如果是(n-j)剩下的操作数为奇数,那么减一 return ans; } int &res=dp[idx][(t-j)&1][n-j][cur+100]; if(res!=-1) return res;//记忆化搜索 if(a[idx]=='F') return res=dfs(idx+1,j,t,cur+(((t-j)&1)?-1:1));//如果是F,那么不转换 if(a[idx]=='T') { return res=max(dfs(idx+1,j,t+1,cur),dfs(idx+1,j+1,t+1,cur+(((t-j)&1)?-1:1)));//转换和不转换的情况 } } int main() { memset(dp,-1,sizeof dp); scanf("%s",a); len=strlen(a); scanf("%d",&n); dfs(0,0,0,0); cout<<ans<<endl; return 0; }
这是比较长一点的代码。。后来为了爬上solution size第一页,我丧心病狂的将代码减到了15行。。。
贴下来纪念一下╰( ̄▽ ̄)╮
代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int n,len,ans,dp[102][2][51][202];char a[102]; int dfs(int idx,int j,int t,int cur){ if(j>n) return 0;if(!a[idx]) return ans=max(ans,(cur>=0?cur:-cur)-((n-j)&1)); if(dp[idx][(t-j)&1][n-j][cur+100]!=-1) return dp[idx][(t-j)&1][n-j][cur+100]; if(a[idx]=='F') return dp[idx][(t-j)&1][n-j][cur+100]=dfs(idx+1,j,t,cur+(((t-j)&1)?-1:1)); if(a[idx]=='T') return dp[idx][(t-j)&1][n-j][cur+100]=max(dfs(idx+1,j,t+1,cur),dfs(idx+1,j+1,t+1,cur+(((t-j)&1)?-1:1))); } int main(){ memset(dp,-1,sizeof dp);scanf("%s%d",a,&n);dfs(0,0,0,0),printf("%d\n",ans); return 0; }
Codeforces 132C. Vasya and Beautiful Arrays【DP,dfs】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。