NYOJ746 整數劃分

該題是一道區間DP的題目，做了幾道區間DP，說起來高大上，也就是DP在區間內的形式而已，核心思想還是要想到轉移->規劃。

題意是在n位數中間加m個稱號，使得最終乘積最大。

狀態轉移方程如下：

dp[ i ][ j ]=max( dp[ i ][ j ],dp[ k ][ j - 1]*a[ k + 1][ i ])

a[ i ][ j ]表示第 i 位到第 j 位組成的數，要預處理一下。

再來說轉移方程，無非兩種情況，加或不加。

在k位不加稱號，便是dp[ i ] [ j ],

如果加了稱號，便是第k+1位到 i 位組成的數與dp [ k ][ j - 1]（k位加了j-1個乘號的最大值）相乘的結果。

在以上兩者中取個最大值，便形成了轉移方程。

代碼如下：

?

#include<iostream>  
#include<string.h>  
#include<algorithm>  
using namespace std;  
#define ll long long 
ll dp[20][20],f,a[25][25];  
int main()  
{  int t,n,m,i,j,b[25];  char s[25],k;  cin>>t;  while(t--)  {  cin>>s>>m;  n=strlen(s);  memset(dp,0,sizeof(dp));  for(i=0;i<n;i++)  b[i]=s[i]-'0';  for(i=0;i<n;i++)  {  f=0;  for(j=i;j<n;j++)  {  f=f*10+b[j];  a[i][j]=f;  }  }  for(i=0;i<n;i++)  dp[i][0]=a[0][i];//沒有乘號時的dp值。  for(i=0;i<n;i++)  for(k=0;k<i;k++)  for(j=1;j<m;j++)  dp[i][j]=max(dp[i][j],dp[k][j-1]*a[k+1][i]);  cout<<dp[n-1][m-1]<<endl;  }  return 0;  
} 

?