DP就是划分子问题,解决子问题而后从子问题的解得到整个问题的解。其实就是分治。
/* * tyvj-1045 * mike-w * 2011-11-6 */ #include<stdio.h> #include<stdlib.h> #include<string.h> #define max(a,b) ((a)>(b)?(a):(b)) #define SIZE 20 int num[SIZE]; int sum[SIZE][SIZE]; int opt[SIZE][SIZE]; int N,K; int main(void) { #ifndef ONLINE_JUDGE freopen("in","r",stdin); #endif int i,j,k; scanf("%d%d",&N,&K); for(i=1;i<=N;i++) scanf("%d",num+i); for(i=1;i<=N;i++) for(j=i;j<=N;j++) sum[i][j]=sum[i][j-1]+num[j]; for(i=1;i<=N;i++) opt[i][0]=sum[1][i]; for(i=2;i<=N;i++) for(j=1;j<=K && j<i;j++) for(k=1;k<i;k++) opt[i][j]=max(opt[i][j],opt[k][j-1]*sum[k+1][i]); printf("%d\n",opt[N][K]); return 0; }