SRM318 div1 medium
rec(0)=(rec(1)+cells[1]+......+rec(6)+cell[6])/6
rec(1)=(rec(2)+cells[2]+......+rec(7)+cell[7])/6
のような連立方程式を解けばいいのは分かったのだけど、そんなの分からない。
というわけで別の方法を考えた。
再帰の深さが1増えるたびに1/6されるから、
ある程度深くなったら誤差で落ちてしまうのではないか
とか思ってビビリながらsubmitしたら通ってしまった。
#include <vector> using namespace std; double cache[15+10][1000+10]; class CyclicGame { public: int n; vector<int> cells; double rec(int pos,int depth) { double &r=cache[pos][depth]; if(1000<depth) r=0.0; else if(r<1000000.0) ; else { r=0.0; for(int i=1;i<=6;i++) r+=(cells[(pos+i)%n]+rec((pos+i)%n,depth+1))/6.0; r=max(r,0.0); } return r; } double estimateBank(vector <int> _cells) { cells=_cells; n=cells.size(); for(int i=0;i<15+10;i++) for(int j=0;j<1000+10;j++) cache[i][j]=1000000.0+10.0; return rec(0,0); } };