BTTCOJ 问题 G: 逃离地牢 树形动规

题目描述

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

输入格式

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

输出格式

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

输入样例

3
12 1 24
6 3 4
4 4 16
0

输出样例

Case #1: 3

解题思路

刚拿到这道题就想到了数字三角形那个题,感觉超级像,一道递推型动规题,读完题发现状态转移方程找不到 – -。 询问了大佬才发现是分解12的质因数2,3,有个小坑就是初始化状态和判断状态转移方程的条件互斥了,所以一直输出0(一次没转移)改完AC,感谢大飞哥的支持,神仙链接: link

AC代码
#include
#define ll long long
using namespace std;
const int maxn=55;//数据大小
struct cp{int s2,s3;}a[maxn][maxn];//存每个位置的2,3数量
int dp[maxn][maxn][1500];//状态数组,下标代表2的数量,值代表3的数量
void init(int n)//初始化函数
{
memset(dp,-1,sizeof(dp));//将状态数组初始化为-1
memset(a,0,sizeof(a));//将原数组初始化为0
dp[0][1][0]=dp[1][0][0]=0;//初始化初始位置的下一步状态为0,因为下面状态转移的条件为-1
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
/*
题目求的是能分解出多少个12,12是由4(2*2)和3,但是算4会有相当一部分大的数据被忽略
例如6,14,18等等,所以这里记录两个最小的质数2,3的数量来代替记录12,后面算2的时候要/2
*/
int t,s2=0,s3=0;//t用来存读入的数据,s2存2的数量,s3存3的数量
scanf("%d",&t);//因为2和3是两个互质的数字,所有一个数拆分的2,3数量互不影响
while(!(t%2))//判断读入的数据最多可以除出多少个2
{
t/=2;
s2++;
}
while(!(t%3))//判断读入的数据最多可以除出多少个3
{
t/=3;
s3++;
}
a[i][j].s2=s2,a[i][j].s3=s3;//将2,3存入原数组
}
}
}
void tree_dp(int n)//dp函数
{
for(int i=1;i<=n;i++)//下标从1开始读,从0开始读状态转移数组下标会越界
{
for(int j=1;j<=n;j++)//同上
{
for(int k=0;k<1500;k++)//k为当前状态2的数量
{
/*下边状态转移方程*/
int temp=max(dp[i-1][j][k],dp[i][j-1][k]);//在2的数量相同的情况下,左边和上边取3大的数字
if(temp!=-1)//条件判断上一层状态分解出了3
{
dp[i][j][k+a[i][j].s2]=temp+a[i][j].s3;//我这一步状态等于上一步的状态加上这一步的2,3形成的新状态
}
}
}
}
}
int main()
{
int n;
int Case=1;//规范输出格式
while(scanf("%d",&n)&&n)//n为0时结束
{
init(n);
tree_dp(n);
int ans=0;//记录答案
for(int i=0;i<1500;i++)//遍历所有状态
{
ans=max(ans,min(dp[n][n][i],i/2));//这边的答案取2,3数量的最小值然后取max更新ans
/*生产零件的道理,向下取整*/
}
cout<<"Case #"<<Case<<": "<<ans<<endl;
Case++;
}
return 0;
}


作者:Mr_渣渣辉