如果有反方向角度凑成最接近180°是最优解,t为角度可以用dp求出,,f[3],f[4]为正反方向前进度数
#include<bits/stdc++.h>
using namespace std;
int x[4];
map<string,int>st;
int dp[18001],s[100],cnt;
int f[4];
double get(double a,double b)
{
return sqrt(a*a+b*b);
}
int main()
{
int n,a;
cin>>n;
st["right"]=1,st["left"]=2,st["forward"]=3,st["backward"]=4;
for(int i=0;i<n;i++)
{
string x;
cin>>x>>a;
f[st[x]]+=a;
if(st[x]==1)s[cnt++]=a;
if(st[x]==2)s[cnt++]=360-a;
}
dp[0]=1;
for(int i=0;i<cnt;i++)
{
for(int j=18000;j>=s[i];j--)dp[j]|=dp[j-s[i]];
}
for(int i=18000;i;i--)dp[i%360]|=dp[i];
double ans=0;
bool flag=0;
for(int i=180,j=180;i;i--,j++)
{
if(dp[i]|dp[j])
{
double t;
if(dp[i])t=i;
else t=j;
t+=180;
t/=180/acos(-1);
double maxx = max(f[3],f[4]),minn=min(f[3],f[4]);
ans=get(maxx+minn*cos(t),minn*sin(t));
flag=1;break;
}
}
if(!flag)
{
ans=abs(f[3]-f[4]);
}
printf("%.15lf\n",ans);
}