View Code of Problem 1031

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#define N 110
#define INF 0x7ffffff
using namespace std;
int dp1[N][N][N];
int dp[N][N][N];
bool ch[N][N][N];
int main()
{
    //freopen("data.txt","r",stdin);
    int dfs(int n,int m,int k);
    int n,m,k;
    while(scanf("%d %d %d",&n,&m,&k)!=EOF)
    {
        for(int i=0;i<=k;i++)
        {
            for(int j=0;j<=i;j++)
            {
                for(int z = 0;z<=m;z++)
                {
                    dp1[i][j][z]=INF;
                }
            }
        }
        for(int z= 0;z<=m;z++)
        {
            dp1[0][0][z] = 0;
        }
        for(int i=1;i<=k;i++)
        {
            for(int j=0;j<=m;j++)
            {
                dp1[i][0][j] = 0;
            }
        }
        for(int i=1;i<=k;i++)
        {
            for(int j=1;j<=i;j++)
            {
                for(int z=1;z<=m;z++)
                {
                    for(int v=1;v*v<=z&&v<=j;v++)
                    {
                        dp1[i][j][z] = min(dp1[i][j][z],dp1[i-v][j-v][z-v*v]+1);
                    }
                }
            }
        }
        memset(ch,false,sizeof(ch));
        dfs(n,k,m);
        if(dp[n][k][m]>=INF)
        {
            printf("0\n");
        }else
        {
            printf("%d\n",dp[n][k][m]);
        }
    }
    return 0;
}
int dfs(int n,int m,int k)
{
    if(ch[n][m][k])
    {
        return dp[n][m][k];
    }
    if(n==1)
    {
        ch[n][m][k] = true;
        dp[n][m][k] = dp1[m][m][k];
        return dp1[m][m][k];
    }
    int Min = INF;
    for(int i=0;i<=m;i++)
    {
        if(dp1[m][i][k]!=INF)
        {
            int w = dfs(n-1,m-i,k-i);
            Min = min(Min,w+dp1[m][i][k]);
        }
    }
    ch[n][m][k] = true;
    dp[n][m][k] = Min;
    return Min;
}