RQNOJ 311 [NOIP2000]乘积最大:划分型dp
题目链接:https://www.rqnoj.cn/problem/311
题意:
给你一个长度为n的数字,用t个乘号分开,问你分开后乘积最大为多少。(6<=n<=40,1<=k<=30)
题解:
简化问题:
给原数字之前添加一个"1 *",乘号不计入数量,对答案无影响。
例如:"1231"可以变成"(1*)1231"。
表示状态:
dp[i][j] = max num(最后一个乘号之前的最大乘积)
i:此时在第i个数的前面添了一个乘号
j:用了j个乘号
例1:"(1*)12*31":
dp[2][1] = 12 (数位从0开始从左向右编号)
例2:"(1*)12*3*1"
dp[3][2] = 12*3 = 36
找出答案:
max dp[i][t] * cal_sec(i,n-1)
cal_sec(x,y)将数字串中[x,y]这个区间的字符串转化为数字
例如:设n=4,t=1.
此时为"(1*)12*31"
则此时这种方案的乘积为dp[2][1]* "31" = 12*31
如何转移:
dp[i][j] = max dp[k][j-1] * cal_sec(k,i-1)
在前面的某一段乘积后面再续上一串数字,达到第i位,用了j个乘号。
前面的某一段乘积:枚举最后一个乘号在第k个数字之前,用了j-1个乘号。
要续的数字:从第k位到i-1位 = cal_sec(k,i-1)
边界条件:
初始时用了0个乘号,但乘积为1。
例如:"(1*)1231".
特判:如果输入的数字就是0,则直接返回0.
注:输入用string,答案用long long存。
数据水。。。否则高精。。。
AC Code:
// state expression:
// dp[i][j] = max num
// i: last '*' is in front of ith bit
// j: used j '*'
//
// find the answer:
// max dp[i][t] * cal_sec(i,len-1)
//
// transferring:
// dp[i][j] = max dp[k][j-1] * cal_sec(k,i-1)
//
// boundary:
// if input == 0: return 0
// else dp[0] = 1, others = -1
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 45
#define MAX_K 35 using namespace std; int n,t;
long long ans;
long long dp[MAX_N][MAX_K];
long long sec[MAX_N][MAX_N];
string s; void read()
{
cin>>n>>t>>s;
} long long cal_sec(int x,int y)
{
if(sec[x][y]!=-) return sec[x][y];
long long res=;
for(int i=x;i<=y;i++)
{
res=res*+s[i]-'';
}
return sec[x][y]=res;
} void solve()
{
memset(sec,-,sizeof(sec));
memset(dp,-,sizeof(dp));
dp[][]=;
for(int i=;i<n;i++)
{
for(int j=;j<=t && j<=i;j++)
{
for(int k=;k<i;k++)
{
if(dp[k][j-]!=-)
{
dp[i][j]=max(dp[i][j],dp[k][j-]*cal_sec(k,i-));
}
}
}
}
ans=;
for(int i=;i<n;i++)
{
if(dp[i][t]!=-) ans=max(ans,dp[i][t]*cal_sec(i,n-));
}
} void print()
{
cout<<ans<<endl;
} int main()
{
read();
solve();
print();
}
最新文章
- jquery移除属性值
- 代码质量管理工具 sonar 配置
- Vim光标定位
- 准备使用 Office 365 中国版--安装
- stdafx.h的作用
- spring定时器设置(转自:http://my.oschina.net/LvSantorini/blog/520049)
- 使用Flexbox实现CSS竖向居中
- Qt 5 常见错误汇总
- 支付宝集成SDK 报错
- 轻松把你的项目升级到PWA
- Spring Security入门(3-6)Spring Security 的鉴权 - 自定义权限前缀
- [Swift]LeetCode594. 最长和谐子序列 | Longest Harmonious Subsequence
- 关于git的诞生
- CANOE入门(三)
- TCP网络协议通信原理(客户端和服务器端)
- Code once, debug everywhere.
- LeetCode——4Sum &;amp; 总结
- Tomcat的overview界面浅析
- bootstrap3中select2的默认值和下拉框的禁用
- ABAP-动态程序生成