背包+贪心

斗神_君莫笑 · 2019-08-15 11:19:02 · 题解

本题需要我们求出最长的离原点距离
那么显然我们可以先走完所有的front,
尝试转到一个离180度最近的角度后走back，
问题就转化为了如何求出一通瞎转后离180度最近的角度，

选取任意旋转后满足某条件
这不就是个变形的01背包嘛
按照01的写法枚举出每一种可能达到的角度
然后挨个遍历取出离180最近的角度
最后余弦公式就解决了
注意计算cos的时候要角度转弧度

#include<bits/stdc++.h>
using namespace std;
int a[410],f[20010];
int main(){
    int n;
    cin>>n;
    int x=0,y=0;
    for(int i=1;i<=n;++i){
        string s;cin>>s;
        int dis;cin>>dis;
        if(s=="forward")x+=dis;
        if(s=="backward")y+=dis;
        if(s=="left"){
            dis=dis%360;
            a[dis]++;
            //cout<<dis<<" "<<a[dis]<<endl;
        }
        if(s=="right"){
            dis=dis%360;
            a[360-dis]++;
        }
    }
    f[0]=1;
    for(int i=0;i<360;++i)
        while(a[i]--)
            for(int j=20000;j>=0;--j)
                if(f[j])f[j+i]++;
    int minn=0x7fffffff;
    for(int i=1;i<=20000;++i)
        if(f[i])
            minn=min(minn,abs(i%360-180));
    if(minn==0){
        printf("%d.000000",x+y);
        return 0;
    }
    printf("%.6f",sqrt((double)x*x+(double)y*y-2*(double)x*(double)y*cos((double)(180-minn)*M_PI/180)));
    return 0;
}