Next, I tried pruning, and always get wrong answer. I think the problem is that I can't deal with the floor functions properly, or that I need a more efficient formulation of the dp.
The following is my tle dp. I think i need something better.
By the way, t is the winning so far, i is the current subject, and k is the number of opponents left in the game.
I think I should remove the t from the dp, and replace with the number of remaining rounds, but I don't see anyway of doing it because I can't decompose the floor functions.
Code: Select all
int f(int t,int i,int k) {
if(k==0) return t;
if(M.find(make_pair(make_pair(t,i),k))==M.end()) {
int r = 0, tt = t-t*p[i]/100;
FOR(l,1,k) {
int v = f(tt+R*l/k,(i+1)%n,k-l);
r >?= v;
}
M[make_pair(make_pair(t,i),k)] = r;
}
return M[make_pair(make_pair(t,i),k)];
}
