SRM 538 DIV1 Medium TurtleSpy

http://apps.topcoder.com/stat?c=problem_statement&pm=11704&rd=14729

問題

命令列が与えられる
"right X", "left X" (X: nat, X <= 359)
右・左にX度回転する。
"forward X", "backward X" (X: nat, 1 <= X <= 1000)
現在の方向に対して前・後にX進む。

これらの命令を入れ替える。ただし"right", "left"は含めなくてもよい。
この命令列を実行して現在の位置からできるだけ離れたい。
最大の距離を答えろ

回答

まず、
最初にforwardを全部使っちゃって、
できるだけ180度に近い角度に回転し、
最後にbackwardで進む。
という戦略が立てられる。
問題はできるだけ180度に近い角度に回転する部分だが、これは単純な、(bool[i][j] := i番目の回転命令まで見た時、j度が可能かどうか) なDPでできる。

コメント

回答・解説は前に見た。
left,rightを含まなくてもいいというのが最初問題読めなかった。Exampleから推測しろ

コード

#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define aut(v, x) __typeof(x) v = (x)
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
typedef long long ll; typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pii> vpii;
const int INF = 0x3f3f3f3f; const ll INFL = 0x3f3f3f3f3f3f3f3fLL;

struct TurtleSpy {
	double maxDistance(vector <string> commands) {
		double b = 0, r = 0;
		vi v;
		each(i, commands) {
			stringstream s(*i);
			string c; int x;
			s >> c >> x;
			if(c == "forward") {
				r += x;
			}else if(c == "backward") {
				b += x;
			}else if(c == "left") {
				v.pb(360-x);
			}else if(c == "right") {
				v.pb(x);
			}
		}
		static bool dp[51][361];
		mset(dp, 0);
		dp[0][0] = true;
		int m = v.size();
		rer(i, 1, m) rer(j, 0, 359) {
			dp[i][j] |= dp[i-1][j];
			dp[i][(j+v[i-1])%360] |= dp[i-1][j];
		}
		rep(i, 360) if(dp[m][i]) cout << i  << endl;
		rer(i, 0, 180) {
			if(dp[m][180-i] || dp[m][180+i]) {
				double xx, yy;
				xx = r + b * cos(i / 360.0 * 3.1415926535897932384626433832795028841971693993751058 * 2.0);
				yy = b * sin(i / 360.0 * 3.1415926535897932384626433832795028841971693993751058 * 2.0);
				r = hypot(xx, yy);
				break;
			}
		}
		return r;
	}
};