[動態規劃]OI練習題：乘法問題 [chf] 解題報告

【問題描述】
設有一個長度為 N 的數字字元串，分成 K+1 個部分，使得 K+1 個部 分的乘積最大。 例如 N=6 ，且數字字元串為 ‘ 310143 ‘ ， K=3. 此時可能有的情況有以 下各種：
3 ＊ 1 ＊ 0 ＊ 143=0
3 ＊ 1 ＊ 01 ＊ 43=129
3 ＊ 1 ＊ 014 ＊ 3=126
3 ＊ 10 ＊ 1 ＊ 43=1290
3 ＊ 10 ＊ 14 ＊ 3=1260
3 ＊ 101 ＊ 4 ＊ 3=3636
31 ＊ 0 ＊ 1 ＊ 43=0
31 ＊ 01 ＊ 4 ＊ 3=372
310 ＊ 1 ＊ 4 ＊ 3=3720
問題：當 N ，數字串， K 給出之後，找出一種分法使其乘積最大。
【輸入格式】
輸入由兩行組成，第一行有兩個整數，n（1≤n≤30）、k（1≤n≤30）；n表示數字串長度、k表示乘號

個數。第二行是數字串。
【輸出格式】
輸出為一個整數，為乘積最大值。
【輸入樣例】
輸入文件名：chf.in
9 4
321044105
輸出文件名：chf.out
5166000
【分析】
動態規劃，和『NOIP2001 乘積最大』一樣。
狀態設定：
F[i,j]：前i個數字添加j個乘號時的最大值。
Num[i,j]：第i的數到第j個的數組成的數，可以在DP前用一個O(N^2)的預處理求出。
狀態轉移方程：
F[i,j]=Max(F[k,j-1]*Num[k+1][i])  (1<=k<=i-1)
目標狀態：  F[N,K]
時間複雜度：O(2*N^2)

【我的代碼】

#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> using namespace std; typedef long long LL; LL N,K; LL num[100][100]; LL F[100][100];   LL Max(LL a,LL b) { if (a>=b) return a; return b; }   LL myatoi(char *str) { LL ret=0; LL sign=1; if(*str=='-') sign=-1; else ret=ret*10+(*str-'0'); str++;   while(*str!= '\0') { ret=ret*10+(*str-'0'); str++; } return sign*ret; }   void init() { cin>>N>>K; char Temp[100]; cin>>Temp; char tmp[100]; for (unsigned int i=1;i<=strlen(Temp);i++) { for (unsigned int j=i;j<=strlen(Temp);j++) { unsigned int ti=i-1; unsigned int tj=j-1; memset(tmp,'\0',sizeof(tmp)); for (unsigned int k=ti;k<=tj;k++) tmp[k-ti]=Temp[k]; num[i][j]=myatoi(tmp); } } }   void dp() { for (int i=1;i<=N;i++) F[i][0]=num[1][i]; for (int j=1;j<=K;j++) { for (int i=1;i<=N;i++) { F[i][j]=0; for (int k=1;k<=i-1;k++) F[i][j]=Max(F[i][j],F[k][j-1]*num[k+1][i]); } } cout<<F[N][K]<<endl; }   int main() { freopen("chf.in","r",stdin); freopen("chf.out","w",stdout); init(); dp(); return 0; }