1021 石子归并
区间dp
1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 int s[1000000],dp[1000][1000],n,m,tot; 5 using namespace std; 6 int main() 7 { 8 memset(dp,0x7f,sizeof(dp)); 9 cin>>n; 10 for(int i=1;i<=n;i++) 11 { 12 cin>>s[i]; 13 s[i]+=s[i-1]; 14 } 15 for(int i=1;i<=n;i++) dp[i][i]=0; 16 for(int i=1;i<=n;i++) 17 for(int j=i-1;j>=0;j--) 18 for(int k=j;k<i;k++) 19 dp[j][i]=min(dp[j][i],dp[j][k]+dp[k+1][i]+s[i]-s[j-1]); 20 cout<<dp[1][n]; 21 return 0; 22 }