一个新的dp模版
【题目描述】
将一圈整数分为m个部分, 使得每个部分的和对10取模后乘积最大
思路:
化环为链+区间dp
设d(l,r,k)是将区间[l,r]分为k段的最优解
那么就有d(l,r,k)=d(l,c,s)*d(c+1,r,k-s)(l<=c<r, 1<=s<k)
答案为max/min{d(i,i+n-1,m)}(1<=i<=n)
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;
const int Mn(115);
const int Mm(15);
int s[Mn];
long long dmn[Mn][Mn][Mm],dmx[Mn][Mn][Mm];
long long fmn(int l,int r,int k) //最大值
{
if(dmn[l][r][k]!=-1) return dmn[l][r][k];
else
{
if(k==1)
{
int ans((s[r]-s[l-1])%10);
if (ans<0) ans += 10;
return dmn[l][r][1] = ans;
}
else
{
long long ans(INT_MAX);
for(int c(l);c<r;++c)
for(int ks(1);ks<k;++ks)
{
if(ks<=c-l+1 && k-ks<=r-c)
ans = min(ans,fmn(l,c,ks)*fmn(c+1,r,k-ks));
}
return dmn[l][r][k]=ans;
}
}
}
long long fmx(int l,int r,int k) //最小值
{
if(dmx[l][r][k]!=-1) return dmx[l][r][k];
else
{
if(k==1)
{
int ans((s[r]-s[l-1])%10);
if (ans<0) ans += 10;
return dmx[l][r][1] = ans;
}
else
{
long long ans(0);
for(int c(l);c<r;++c)
for(int ks(1);ks<k;++ks)
{
if(ks<=c-l+1 && k-ks<=r-c)
ans = max(ans,fmx(l,c,ks)*fmx(c+1,r,k-ks));
}
return dmx[l][r][k] = ans;
}
}
}
int main()
{
int n,m;
cin >> n >> m;
for(int i(1);i<=n;++i)
scanf("%d",s+i),s[i+n]=s[i];
memset(dmn,-1,sizeof dmn);
memset(dmx,-1,sizeof dmx);
for(int i(1);i<2*n;++i) s[i] += s[i-1]; //前缀和优化区间和
long long Min(INT_MAX),Max(0); //寻找最优解
for(int i(1);i<=n;++i)
{
Min = min(Min,fmn(i,i+n-1,m));
Max = max(Max,fmx(i,i+n-1,m));
}
cout << Min << endl << Max;
return 0;
}
近期评论