首页 > 代码库 > 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】