prasoonjha1
May '23

I am getting WA on problem Breaking String20,I am using Knuth’s optimization but I don’t understand what is the issue with following code. Same code worked fine with Cutting sticks2 (which is very similar to this) problem in UVA.

int32_t main()
{
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);
    //int t=2;
    //scanf("%d",&t);
    while(!cin.eof())
    {
        int n,m;
        cin>>n>>m;
        vector<int> v(m+2);
        for(int i=1;i<m+1;i++)    
        {
            cin>>v[i];
            //v[i] = (rand()%(n-1)+1);
        }
        v[m+1] = n;
        sort(v.begin(),v.end());
        vector<vector<int>> dp(m+2,vector<int>(m+2,1e9));
        vector<vector<int>> opt(m+2,vector<int>(m+2,1e4));

        for(int i=0;i<m+2;i++)
        {
            dp[i][i] = 0;
            opt[i][i] = i;
        }

        for(int i = m;i>=0;i--)
        {
            for(int j=i+1;j<m+2;j++)
            {
                int ans = 1e9;
                for(int k = opt[i][j-1];k<=min(j-1,opt[i+1][j]);k++)
                {
                    //cout<<dp[i][k]+dp[k][j]+(v[j]-v[i])<<"\n";
                    if(ans>=(dp[i][k]+dp[k][j]+(v[j]-v[i])))
                    {
                        ans = (dp[i][k]+dp[k][j]+(v[j]-v[i]));
                        opt[i][j] = k;
                    }
                }
                if(ans!=1e9)    dp[i][j] = ans;
                else
                {
                    dp[i][j] = 0;
                    opt[i][j] = i;
                }
            }
        }
        cout<<dp[0][m+1]<<"\n";

    }
    return 0;
}