大概思路是用$f[i][j]$表示當前執行到第$i$個操作，改變了$j$次時回到原點的最大次數，并且此時剛好在原點（這是為了方便轉移）。然后每次只需要枚舉一個$k$，計算出執行完$(i,k]$這一段操作后再回到原點需要修改幾個，就可以進行轉移。
少寫了一句判斷狀態是否可行害得我懵逼了好久（感謝xLLLx幫我Debug）

#include <bits/stdc++.h> using namespace std; const int N=301; int n,f[N][N],mx,u[N],r[N];class FriendlyRobot { public:int findMaximumReturns( string s, int m ); };int d(int k,int i){ //執行k個與i個操作之后都在(0,0)，中間需要改多少個，利用了類似前綴和的思想int x=abs(u[i]-u[k]),y=abs(r[i]-r[k]);return (x+y)/2; }int FriendlyRobot::findMaximumReturns(string s, int m) {n=s.size();for(int i=0;i<n;i++)if (s[i]=='U'||s[i]=='D'){if (s[i]=='U') u[i+1]=u[i]+1;else u[i+1]=u[i]-1;r[i+1]=r[i];} else{if (s[i]=='R') r[i+1]=r[i]+1;else r[i+1]=r[i]-1;u[i+1]=u[i];}memset(f,-1,sizeof f);for(int i=0;i<=n;i+=2) if (!u[i]&&!r[i]) f[i][0]=0; //這句應該沒用mx=0;for(int i=0;i<=n;i+=2)for(int j=0;j<=i/2&&j<=m;j++){if (f[i][j]==-1) continue; //必須要判斷當前狀態是否可行（否則會WA得很慘mx=max(mx,f[i][j]);for(int k=i+2;k<=n;k+=2){int w=d(i,k);if (j+w<=m) f[k][j+w]=max(f[k][j+w],f[i][j]+1);}//printf("f[%d][%d]=%d\n",i,j,f[i][j]);}return mx; }

總結

以上是生活随笔為你收集整理的TopCoder SRM 682 Div2 1000 FriendlyRobot的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。