SRM304 div2 hard

幾何＋DP。
問題文見て「あ、幾何や。やめとこ。」と思い、すぐに解説を探したけど幾何の部分も大したことはなかった。

DPも大したことはないけど、１点だけ注意が必要。
それは頂点[0]と頂点[n-1]は隣り合っているので同時に使ってはいけないという点。

参考にさせていただいたページ：
SRM 304 PolyMove - hama_DU@TopCoderへの道 - TopCoder部

#include <cmath>
#include <vector>

using namespace std;

class PolyMove
{
	public:

		double getInc(double x1,double y1,double x2,double y2)
		{
			double xd=x1-x2,yd=y1-y2;
			return sqrt(xd*xd+yd*yd)/2.0;
		}

		double addedArea(vector <int> _x, vector <int> _y)
		{
			int n=_x.size();
			vector<double> x(n),y(n),inc(n);
			for(int i=0;i<n;i++)
				x[i]=_x[i],y[i]=_y[i];
			for(int i=1;i<n-1;i++)
				inc[i]=getInc(x[(i-1+n)%n],y[(i-1+n)%n],x[(i+1+n)%n],y[(i+1+n)%n]);

			double ans;
			double DP[55];
                        
                        //inc[n-1]を使う場合
			DP[n]=0.0;　　//これは番兵的存在
			DP[n-1]=inc[n-1];
			for(int i=n-2;1<=i;i--)
				DP[i]=max(DP[i+2]+inc[i],DP[i+1]); 
　　　　　　　　　　　　　　　　//inc[i]を使うならinc[i+1]は使えない
			ans=DP[1];

                        //inc[0]を使う場合
			DP[n]=0.0;
			DP[n-1]=0.0;
			for(int i=n-2;0<=i;i--)
				DP[i]=max(DP[i+2]+inc[i],DP[i+1]);

			ans=max(ans,DP[0]);

			return ans;
		}
};