一道题DP

时间：2020-12-04 17:56:44

Problem Description

小明明又被大威鱼抓住了，大威鱼把小明明关在地牢里，地牢由n * n 个房间组成，小明被困在地牢的最左上角的房间中，出口在最右下角，他想逃出这个诡异的地牢，但是他只能向下或者向右走。
小明每经过一个房间，都要受到一定的伤害(伤害都大于0)，而且这个伤害可不是累加的哦，是累乘的，因此当他走出地牢的时候，他受到的伤害会非常大。但是小明有一个终极技能，能把受到的伤害X转变为金币，转化如下。
int val(type x) {
  int ret = 0;
  while(x % 12 == 0) {
    x /= 12;
    ret++;
  }
  return ret;
}
请问小明最多能得到多少金币？

Input

输入包含多组测试用例，每组测试用例的第一行是一个整数n(n <= 50)，接下来n行每行n个正整数 (<= 10 ^ 9) 表示每个房间对小名造成的伤害，当n = 0 时输入结束。

Output

先输出Case，Case数从1开始，再输出小明获得的最大金币，具体输出形式见样例。

Sample Input

3

12 1 24

6 3 4

4 4 16

0

Sample Output

Case #1: 3
解析：
    12可以分为2*2*3；
    那么答案就是统计min(2的个数/2,3的个数）的最大值；
   如果直接记录2的个数，3的个数为状态的话，50*50*乘积中2的幂次*3的幂次，内存不够。
   于是想到只将3的幂次作为一种状态，然后记录沿途能达到的2的个数。
   状态方程

   F[I][J][K]表示能够有2因子的个数，没有就为-1；
   Temp=max(F[I-1][J][K],F[I]J-1][K]);
   F[I][J][K+MP[I][J].Y]=TEMP+MP[I][J].X;
  注意边界；
具体看代码了;
#include<cstdio>

#include<cstring>

#include<string>

#include<queue>

#include<algorithm>

#include<vector>

#include<set>

#include<map>

#define INF 999999999

#define N   100000

using namespace std;

struct node

{

    int x,y;

}mp[][];

int dp[][][];

int main()

{

     int t=;

     int n;

       while (scanf("%d",&n)!=EOF&&n){

            printf("Case #%d: ",++t);

            memset(mp,,sizeof(mp));

            memset(dp,-,sizeof(dp));//初始化为-1，

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

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

            {

                int xx,yy;

                scanf("%d",&xx);

                yy=xx;

                while (yy%==)//记录元素是2的多少次方

                {

                 mp[i][j].x++;

                 yy/=;

                }

                while (xx%==)记录元素是3的多少次放

                {

                    mp[i][j].y++;

                    xx/=;

                }

            }

            dp[][][]=;

            for (int i=;i<=n;i++) dp[][i][]=,dp[i][][]=;//边界

          for (int i=;i<=n;i++)//状态转移

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

               for (int k=;k<=;k++)//1200是自己随便写的一个状态，可能实际没有这么多

               {

                  int temp=max(dp[i-][j][k],dp[i][j-][k]);//考虑DP[I-1][J][K],DP[I][J-1][K]都可能为-1

                  if (temp>-)

                  dp[i][j][k+mp[i][j].y]=mp[i][j].x+temp;　

              }

        int ans=;

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

        ans=max(ans,min(dp[n][n][i]/,i));

        printf("%d\n",ans);

     }

    return ;

}

相关文章