bg2d
BAN USERFirst lets solve this problem as an array, rather than a circle.
dp[i][j] denotes the maximum value we can get, when in the first i bombs, the last bomb activated is j.
val[i] is the value of bomb i. effect[i] is the influence range of bomb i.
dp[i][i] = max(dp[i-1][k])+val[i], where k<j and k+effect[k]<j and j-effect[j]>k
dp[i][j] = dp[i-1][j] when j<i (obviously, cuz in this case no new bomb is activated);
The answer is max(dp[n][i], i=1...n)
How do we apply this to a circle? It's easy, lets just duplicate the N elements to form 2N element array so that bomb[1..n] are the original elements, bomb[i = n+1...2n] = bomb[i-n];
Then we can apply the above dynamic function. But notice that any bomb on a circle can be the starting bomb, so we need to iterate through 1 to N as the starting bomb, and make sure when it is the starting bomb, it is activated.
The code is as follows:
1. Duplicate N-element circle into 2N elements array
Int ans=0;
For (int i=0;i<n;i++) {
Dp[i]=val[i];
Ans=max(dp[i],ans);
For (int j=i+1;i<=i+n-1;j++) dp[i]=-1;
For (int j=i+effect[i]+1;j< i+n-effect[i];j++)
If (j-effect[j]>I && j+effect[j]<i+n)
{
For (int k=j-effect[j]-1;k>=I;k--)
If (k+effect[k]<j)
Dp[j]=max(dp[j],dp[k]);
Dp[j]+=val[j];
Ans=max(ans,dp[j]);
}
}
I dont think this works. Lets take "babbaa" as an example.
- bg2d January 01, 2015Correct answer should be : bbaa
Follow your algorithm:
1. break babbaa into bab baa
for bab, if we break it, the resulting two substrings are ba and b; thus we need to choose between the two largest suffix bab(ba+b) and b. bab is lexicographicaly larger, so we return bab;
similarly, the maximum suffix of baa is baa. now we compare babbaa and baa, the result is babbaa.
However, the correct answer should be bbaa.