QUST日常訓練(1)積最大
2497 ワード
タイトルの説明
多くの学校では比較的な習慣が流行している.先生たちは聞くのが好きで、○○から○○までの中で、点数が一番高いのはいくらですか.
これは多くの学生に反感を感じさせて、あなたが喜ぶかどうかにかかわらず、今あなたがしなければならないのは、先生の要求に従って、プログラムを書いて、先生の質問をシミュレートすることです.もちろん、先生はある同級生の成績を更新する必要があることがあります.
入力
この問題には複数のテストが含まれています.ファイルが終わるまで処理してください.各試験の第1行において、2つの正の整数NおよびMは、それぞれ学生の数および操作の数を表す.学生ID番号はそれぞれ1編からNまでです.2行目はN個の整数を含み、このN個の学生の初期成績を表し、i番目の数aiはIDがiの学生の成績を表す.次はM行です.各行には1文字C('Q'または'U'のみ)と2つの正の整数A,Bがある.Cが「Q」である場合、IDがAからB(A,Bを含む)までの学生の中で、成績が最も高いかを尋ねる質問操作であることを示す.Cが「U」の場合、IDがAの学生の成績をBに変更する更新操作であることを示す.
しゅつりょく
対応する問い合わせを出力します.
サンプル入力
5 61 2 3 4 5Q 1 5U 3 6Q 3 4Q 4 5U 2 9Q 1 5
サンプル出力
5659
ヒント
【データの説明】
30%のデータに対して、0
F(N,K)が文字列の前のNビットにK個の乗数を挿入して得られる最大値であると仮定し,F(N,K)とF(N−1,K),F(N−1,K−1)の関係を考慮すると?
添付例:
312:N=3,K=1のとき、N=1,K=0からF(1,0)=3 F(2,0)=31 F(3,1)=max(F(1,0)*12,F(2,0)*2)=max(36,62)=62を導出する
31245:N=5,K=2,F(1,0)からF(1,0)=3 F(2,0)=31 F(3,0)=312 F(2,1)=3*1=3 F(3,1)=max(F(1,0)*12,F(2,0)*2)=max(36,62)=62 F(4,1)=max(F(1,0)*124,F(2,0)*24, F(3, 0) * 4) = max(372, 744, 1248) = 1248 F(5, 2) = max(F(2, 1) * 245, F(3, 1) * 45, F(4, 1) * 5) = max(735, 2790, 6240) = 6240
動的計画方程式:A[I,Num]B[I,Num]を最初の数字からI番目の数字にNum個の乗数を加えた最大値とし、s[k,I]がk番目からI番目の数字を表すとB[I,Num]=max(A[k,Num-1]*S[k+1,I])1+Num-1<=k<=Iとする.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n,k;
char ch[45];
cin>>n>>k;
scanf("%s",ch+1);
int f[45],asum=0;
for (int i=1;i<=n-k;i++) // *
{
asum=asum*10+ch[i]-'0';
f[i]=asum;
}
for (int tk=1;tk<=k;tk++)
{
for (int tn=n-k+tk;tn>=tk+1;tn--)
{
f[tn]=-1;
char temp[45];
for (int j=tk;j<=tn-1;j++) // f[tn]
{
memcpy(temp,ch+j+1,tn-j);
temp[tn-j]=0;
if (f[tn] < f[j]*atoi(temp)) f[tn]=f[j]*atoi(temp); //atoi（） int
}
}
}
printf("%d
",f[n]);
return 0;
}