问题标题: 酷町堂：1522 六分题，萌新勿点

Question

0

已解决

黄子扬

初级天翼

mem={}
def dp(pos,k):
	if k==1:
		return int(s[0:pos])
	if(pos,k) in mem:
		return mem[(pos,k)]
	res=0
	for x in range(k-1,pos):
		res=max(res,dp(x,k-1)*int(s[x:pos]))
	mem[(pos,k)]=res
	return res

n,k=map(int,input().split())
s=input().strip()
print(dp(n,k+1))

因为是高精度，所以写了python，洛谷原题AC，酷町堂却全部RE

@赵逸凡大佬我记得您A了这道题，帮忙看下呗

顺便吐槽一句大家可以放心地认真刷题，赛季排行的前几名（笃定）马上就要消失了

例如现在榜一8/2，你可以看到他的作业题还是char，xswl

黄子扬在2020-08-02 08:59:48追加了内容

别问我6分题为什么代码这么短（（（

黄子扬在2020-08-02 09:00:53追加了内容

3207同题仍然RE了，求原因

黄子扬在2020-08-02 09:33:27追加了内容

啊这被查看了十几次没人说一句话，是题目太难还是不会python啊大家

Answer 1

已采纳

赵逸凡

初级启示者

为什么这道题我酷町堂原题AC，洛谷WA 20分

python很少有人学到吧，反正我没学（不是竞赛语言）

这道题我是用dp做的，这样比搜索好推导。

显然这道题是个多重背包，而且是线性dp，思路很具有技巧，有考虑进位，强制类型转换

我写的定义：

int num[50][50],f[50][10];
char s[50];

s是要输入的，f是动态转移数组，num是将i与j(i<=j<=n)组合得到的数

Answer 2

王泽宇

初级光能

for(int i=1;i<=n;i++)
        f[i][0]=num[1][i];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=min(K,i-1);j++){
            for(int k=1;k<i;k++){
                f[i][j]=max(f[k][j-1]*num[k+1][i],f[i][j]);
            } 
        }
    }
    cout<<f[n][K];

开头输入s+1

王泽宇在2020-08-02 12:40:07追加了内容

int n,K;
cin>>n>>K;
cin>>s+1;
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
num[i][j]=num[i][j-1]*10+s[j]-'0';
}
}

问题标题: 酷町堂：1522 六分题，萌新勿点

2 个回答: