noi 6047 分蛋糕

题目链接：http://noi.openjudge.cn/ch0405/6047/

和Uva1629很类似，不过，可能用记忆化难写一点，状态初始化懒得搞了。就用循环好了。

状态描叙也可以修改，那个题目是由于有樱桃的坐标，所以用四维，而这个题目只要长宽，和块数就OK了，三维，然后还是死遍历所有情况的切割。

 #include<iostream>

 #include<algorithm>

 using namespace std;

 int dp[][][];

 int main()

 {

     int n,m,c;

     for(int i=; i<=; i++)

     {

         for(int j=; j<=; j++)

         {

             dp[i][j][]=i*j;

         }

     }

     for(int i=; i<=; i++)

     {

         for(int j=; j<=; j++)

         {

             for(int k=; k<=; k++)

             {

                 for(int l=; l<i; l++)

                 {

                     for(int p=; p<k; p++)

                     {

                         if(dp[i][j][k]!=) dp[i][j][k]=min(max(dp[i-l][j][k-p],dp[l][j][p]),dp[i][j][k]);

                         else dp[i][j][k]=max(dp[i-l][j][k-p],dp[l][j][p]);

                     }

                 }

                 for(int l=; l<j; l++)

                 {

                     for(int p=; p<k; p++)

                     {

                         if(dp[i][j][k]!=) dp[i][j][k]=min(dp[i][j][k],max(dp[i][j-l][k-p],dp[i][l][p]));

                         else dp[i][j][k]=max(dp[i][l][k-p],dp[i][j-l][p]);

                     }

                 }

             }

         }

     }

     while(cin>>n>>m>>c)

     {

         if(n==&&m==&&c==) break;

         printf("%d\n",dp[n][m][c]);
     }

     return ;

 }

巴特西

noi 6047 分蛋糕

最新文章

热门文章