Hi , was trying to solve the problem
http://codeforces.net/contest/543/problem/A
using the following algo
for(int i=0;i<=n;i++)
{
for(int j=0;j<=b;j++)
dp[i][j][0]=1;
}
for(int k=1;k<=m;k++)
{
for(int j=0;j<=b;j++)
{
for(int i=1;i<=n;i++)
{
dp[i][j][k]=(dp[i-1][j][k]+dp[i][j][k])%mod;
if(j-arr[i]*1>=0)
dp[i][j][k]=(dp[i][j][k]+dp[i][j-arr[i]][(k-1)])%mod;
}
}
}
where dp[i][j][k] means answer for the first i members with maximum error begin j and writing k lines ans is dp[n][b][m] but it's memory is too much.
So i optimised it as
for(int k=1;k<=m;k++)
{
for(int j=0;j<=b;j++)
{
for(int i=1;i<=n;i++)
{
dp[i][j][k&1]=(dp[i-1][j][k&1]+dp[i][j][k&1])%mod;
if(j-arr[i]*1>=0)
dp[i][j][k&1]=(dp[i][j][k&1]+dp[i][j-arr[i]][(k-1)&1])%mod;
}
}
for(int j=0;j<=b;j++)
{
for(int i=1;i<=n;i++)
dp[i][j][(k-1)&1]=0;
}
}
ans is dp[n][b][m&1] but this is getting wrong answer.Someone help.
Instead of the dp state that you've described, consider the following dp state. DP[i][j] will correspond to the subproblem with i lines of code and exactly j mistakes. Then to move to state DP[i+1][k], all we need to do is to iterate over the states DP[i][*] with each programmer. The complexity will be O(N^3). Hope this helps.