有一条豪华游轮（其实就是条小木船），这种船可以执行4种指令：

right X : 其中X是一个1到719的整数，这个命令使得船顺时针转动X度。

left X : 其中X是一个1到719的整数，这个命令使得船逆时针转动X度。 forward X : 其中X是一个整数（1到1000），使得船向正前方前进X的距离。

backward X : 其中X是一个整数（1到1000），使得船向正后方前进X的距离。

随意的写出了n个命令，找出一个种排列命令的方法，使得船最终到达的位置距离起点尽可能的远。

输入格式：

第一行一个整数n(1 <= n <= 50)，表示给出的命令数。

接下来n行，每行表示一个命令。

输出格式：

一个浮点数，能够走的最远的距离，四舍五入到6位小数。

输入样例#1：

3
forward 100
backward 100
left 90

输出样例#1：

141.421356

贪心思想。命令可以随意排列，那么开场肯定是全军突击（误），把所有前进指令都用完（走一半拐弯再走，肯定不如全程直走好），然后转向，尽可能接近180°，再倒着走。

求最适合的转向角度，我选择偷懒暴搜。偷懒的结果就是50分，剩下50分T掉了。

/*by SilverN*/
#include
#include
#include
#include
#include
using namespace std;
const int mxn=;
const double pi=3.141592653;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();} return x*f; } double an[mxn]; double fw[mxn]; double nx,ny; int acnt=,rcnt=; double dist(double x1,double y1,double x2,double y2){ return sqrt( (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2) ); } int n; double ans=; double ttd=; void dfs(int rk,double now){ // printf("%d %.4f\n",rk,now); if(rk>acnt){
double tnow=fabs(now);
double tmpx=nx+ttd*sin(tnow*pi/);
double tmpy=ny+ttd*cos(tnow*pi/);
// printf("%d %.4f %.4f\n",rk,tmpx,tmpy);
ans=max(ans,dist(tmpx,tmpy,,));
return;
}
dfs(rk+,now);
// printf("%.5f\n",now+an[rk]);
dfs(rk+,now+an[rk]);
return;
}
int main(){
n=read();
int i,j;
char ch[];double x;
nx=ny=;
for(i=;i<=n;i++){ scanf("%s%lf",ch,&x); if(ch[]=='f'){ fw[++rcnt]=x; } if(ch[]=='b'){ fw[++rcnt]=-x; } if(ch[]=='l'){ an[++acnt]=-x; // printf("in:%d",acnt); if(an[acnt]<-)an[acnt]+=; } if(ch[]=='r'){ an[++acnt]=x; if(an[acnt]<)an[acnt]-=; } } ttd=; for(i=;i<=n;i++){ if(fw[i]>)
ny+=fw[i];
else ttd+=fw[i];
}
sort(an+,an+acnt+);
dfs(,);
//
//
/* printf(" %d\n",dgans);
nx+=ttd*cos(dgans);
ny+=ttd*sin(dgans);*/
// printf("%.4f %.4f\n",nx,ny);
printf("%.6f\n",ans);
return ;
}

DFS

正解是DP。懒得写了，从rlt那里抄了代码233

#include
#include
#include
#include
using namespace std;
const double pi=3.1415926535;
int n,sf,sb,p,ang[];
double ans;
bool f[][];
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
int x;
char ch[];
scanf("%s%d",ch,&x);
if(ch[]=='f')
sf+=x;
if(ch[]=='b')
sb+=x;
if(ch[]=='r')
ang[++ang[]]=x;
if(ch[]=='l')
ang[++ang[]]=-x;
}
f[][]=;
for(int i=;i<=ang[];i++)
for(int j=;j<;j++)
if(f[i-][j])
f[i][j]=,f[i][(j+ang[i]+)%]=;
p=;
for(int i=;i<;i++)
if(f[ang[]][i])
p=min(p,abs(i-));
ans=sqrt(sf*sf+sb*sb+*sb*sf*cos(p*pi/));
printf("%.6f\n",ans);
return ;
}

正解dp