首页 > 代码库 > Codeforces 132C. Vasya and Beautiful Arrays【DP，dfs】

Codeforces 132C. Vasya and Beautiful Arrays【DP，dfs】

2024-07-19 09:35:36   222人阅读

题目大意：

在一根数轴上有一只机器龟，它能够听从人们给它的指令做出向前走一步（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】


联系
我们