蓝桥杯练习系统试题
#include<stdio.h> #include<stdlib.h> #include<string.h> int dp[1000][1000]; int d[1000][1000]; void f(int n,int shi[]) { for(int i=0;i<n;i++) { dp[i][i]=0; } for(int r=2;r<=n;r++) for(int i=0;i<n-r+1;i++) { int j=i+r-1; dp[i][j]=d[i][i]+d[i+1][j]+dp[i][i]+dp[i+1][j]; for(int k=i+1;k<j;k++) { int t; t=d[i][k]+d[k+1][j]+dp[i][k]+dp[k+1][j]; if(t<dp[i][j]) dp[i][j]=t; } } } int main() { int n; int shi[1000]; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",&shi[i]); } for(int i=0;i<n;i++) { d[i][i]=shi[i]; } for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { d[i][j]=d[i][j-1]+shi[j]; } } f(n,shi); printf("%d",dp[0][n-1]); return 0; }