题目描述
有一条豪华游轮（其实就是条小木船），这种船可以执行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°走完后退的步数
可实际的转向并不见得那么顺心。
于是我们可以这么处理：
1、先把前进的走完【没必要转向因为无论往那么方向走都一样】
2、先通过几次旋转，旋转出离180°最近的角度
3、把后退的走完
4、把剩下的转完。。。。。
现在问题就转化为了如何求出最接近180°的角度
显然这就是一个背包dp问题：
我们可以利用同余，把所有的旋转都转化为同一方向0~359°之间的角度，然后就进行状态转移就行了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=55,maxm=400,INF=200000000;
inline int read(){
int out=0,flag=1;char c=getchar();
while(c<48||c>57) {if(c=='-') flag=-1;c=getchar();}
while(c>=48&&c<=57) {out=out*10+c-48;c=getchar();}
return out*flag;
}
int N,dp[maxn][maxm],fw=0,bw=0,v[maxn],m=0;
char s[maxn];
int main()
{
const double PI=acos(-1);
int x,r;
N=read();
for(int i=1;i<=N;i++){
scanf("%s%d",s,&x);
if(s[0]=='f') fw+=x;
else if(s[0]=='b') bw+=x;
else if(s[0]=='r'){
v[++m]=x%360;
}
else{
v[++m]=(-x+720)%360;
}
}
dp[0][0]=true;
for(int i=1;i<=m;i++)
for(int j=0;j<360;j++){
dp[i][j]=dp[i-1][j]||dp[i-1][(j-v[i]+360)%360];
}
r=180;
for(int i=0;i<180;i++)
if(dp[m][180-i]||dp[m][180+i]) {r=i;break;}
double temp=fw+(double)bw*cos(r/180.0*PI),t=(double)bw*sin(r/180.0*PI);
double ans=sqrt(temp*temp+t*t);
printf("%.6lf
",ans);
return 0;
}
其实这道题的dp还是很有启发性的，给我们展现了一种环状背包转移的模式。