P1773 符文之语_NOI导刊2010提高（02）

· · 题解

前言

这道题是真的恶心，我肝了一个晚上……

这是P1773 符文之语_NOI导刊2010提高（02）的题解。一道****（无法用语言形容）的DP题，今早考试里被它虐的死去活来（我好蒟啊）。这道题从第一眼看到它我就知道是DP，等到讲题前都没能设出状态……

我们以乘号划分阶段，即f[i][j]表示到第i个数字，满足最小乘积（对m取余后的）所需要划分的阶段（要加的括号）。sum[i][j]表示从第i个数字到第j个数字的乘积对m取余。

DP可以从小到大推，也可以从大到小推，看各位习惯。这里只提供从小到大推的程序（个人习惯）

在程序中的所有乘积后都要记得对m取余（非常重要）

Code

#include<cstdio>
#include<cstring>
using namespace std;
int f[1010][60],sum[1010][1010],m,lon;
char zfc[1010];
int main()
{
    memset(f,0x7F,sizeof(f));//因为我是从前到后推的，所以我一开始把f数组定义成无穷大
    scanf("%s\n%d",zfc,&m);//先输入字符串，不要忘记换行 
    lon=strlen(zfc);//lon记录字符串的长度 
    for(int i=1;i<=lon;i++)//sum[i][i]表示从字符串的第i个到第i个的乘积
        sum[i][i]=zfc[i-1]-'0';//当前这一位到自己只有一位啊，所以取不取余倒也没有什么关系 
    for(int i=lon;i>=1;i--)//i是从后往前查的 
        for(int j=i+1;j<=lon;j++)//j从前往后查，所以f[i][j-1]显然是已经知道了的 
            sum[i][j]=(sum[i][j-1]*10%m+sum[j][j])%m;//从i到j显然是i到j-1位的乘积乘10加上当前这一位 
    for(int i=1;i<=lon;i++)//f[i][sum[1][i]]表示从第1个点到第i个点时乘积为sum[1][i]所要加的乘号 
        f[i][sum[1][i]]=0;//仔细想一想，一个乘号都不用加，乘积为sum[1][i]的数就是字符串前i位的乘积 
    for(int i=1;i<=lon;i++)//枚举字符串 
        for(int j=1;j<i;j++)//从j到i的区间 
            for(int k=0;k<m;k++)//乘积取余，求的是答案 
                if(f[j][k]+1<f[i][k*sum[j+1][i]%m])//如果在第j个数字后放乘号能比原来的决策好 
                    f[i][k*sum[j+1][i]%m]=f[j][k]+1;//更新 
    for(int i=0;i<m;i++)//从小到大推肯定要从前面找答案啊，如果不是0x7F说明这个状态存在 
        if(f[lon][i]<0x7F)
        {
            printf("%d %d ",i,f[lon][i]);//不输出等啥呢？ 
            break;
        }
    for(int i=m;i>=0;i--)//最大值同理啊 
        if(f[lon][i]<0x7F)
        {
            printf("%d %d",i,f[lon][i]);
            break;
        }
    return 0;
}

这道题主要是状态难设，其他倒也没有什么。所以大家要努力攻克DP啊。

方程不规范，爆零两行泪……