題目
題目描述
丁丁最近沉迷于一個數字游戲之中，這個游戲看似簡單，但丁丁在研究了許多天之后卻發覺原來在簡單的規則下想要贏得這個游戲并不那么容易，游戲是這樣的，在你面前有一圈整數（一共n個），你要按順序將其分為m個部分，各部分內的數字相加，相加所得的m個結果對10取模后再相乘，最終得到一個數k，游戲的要求是使你所得的k最大或者最小，
例如，對于下面這圈數字（n=4，m=2）：
當要求最小值時，((2-1) mod 10)×((4+3) mod 10)=1×7=7，要求最大值時，為((2+4+3) mod 10)×(-1 mod 10)=9×9=81，特別值得注意的是，無論是負數還是正數，對10取模的結果均為非負值，
丁丁請你撰寫程式幫他贏得這個游戲，
輸入
輸入檔案第一行有兩個整數，n（1≤n≤50）和m（1≤m≤9），以下n行每行有個整數，其絕對值不大于104，按順序給出圈中的數字，首尾相接，
輸出
輸出檔案有兩行，各包含一個非負整數，第一行是你程式得到的最小值，第二行是最大值，
樣例輸入
4 2
4
3
-1
2樣例輸出
7
81題目大意
輸入n,m和n個整數，要求把這n個整數環形排列后分成m個部分，求每個部分的和mod10后乘起來的積最大或最小
演算法
這道題是個人都知道用動態規劃，我們設表示把區間(
)分成k份的最小乘積，
表示把區間(
)分成k份的最大乘積， 設
表示第
個元素的前綴和，則
=
-
，因為把一段元素分成一份，它的最大值也是唯一值就是該份的元素的總和，
我們可以把的某段元素提取出來，加到第
份中，假設我們把第
個元素提取出來，則
=min{
×
-
-
}(
)，即把第
到
的元素全部加到第k份里之所以可以這樣，是因為丁丁只讓我們選取一段連續的元素作為一個部分，
最后我們只要輸出min{}(
)即可，
g陣列同理，怎么改留作思考，
注意：要把a陣列復制一遍，變成環，
代碼
#include <cstdio>
#define ll long long
using namespace std;
const ll INF=0x7ffffffffffffff/3;
const int N=105,M=15;
ll a[N],s[N],f[N][N][M],g[N][N][M];//不用long long會WA掉的，
ll max(ll x,ll y)
{
if (x>y) return x;
return y;
}
ll min(ll x,ll y)
{
if (x<y) return x;
return y;
}
ll mod(ll x)//方面mod10
{
return (x%10+10)%10;
}
int main()
{
int n,m;
ll ans1=INF,ans2=-INF;
scanf("%d %d",&n,&m);
for (int i=1; i<=n; i++)
{
scanf("%lld",&a[i]);
a[n+i]=a[i];//復制成環
}
s[0]=0;
for (int i=1; i<=2*n; i++) s[i]=s[i-1]+a[i];
for (int i=1; i<=2*n; i++)
for (int j=1; j<=2*n; j++)
{
f[i][j][1]=mod(s[j]-s[i-1]);//初始化fi,j,1
g[i][j][1]=mod(s[j]-s[i-1]);//初始化gi,j,1
}
for(int i=1;i<=2*n;i++)
for(int j=i;j<=2*n;j++)
for(int k=2;k<=m;k++)
f[i][j][k]=INF; //因為f存的是最小值，所以要把它初始化為∞，
for (int k=2; k<=m; k++)
for (int i=k; i<=n; i++)
for (int j=1; j<=2*n-i+1; j++)
{
for (int u=j; u<j+i-1; u++)
{
f[j][j+i-1][k]=min(f[j][j+i-1][k],f[j][u][k-1]*mod(s[j+i-1]-s[u]));
g[j][j+i-1][k]=max(g[j][j+i-1][k],g[j][u][k-1]*mod(s[j+i-1]-s[u]));
}
}
for (int i=1; i<=n; i++)
{
ans1=min(ans1,f[i][i+n-1][m]);//求出min{fi,i+n-1,m}
ans2=max(ans2,g[i][i+n-1][m]);
}
printf("%lld\n%lld",ans1,ans2);
return 0;
}轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/289398.html
標籤：其他
下一篇：趙神牛的游戲