rip 初始 tag 结束 位置 int span 题目
1048 石子归并 codevs
题目描述 Description
有 n 堆石子排成一列,每堆石子有一个重量 w[i], 每次合并可以合并相邻的两堆石子,一次合并的代价为两堆石子的重量和 w[i]+w[i+1]。问安排怎样的合并顺序,能够使得总合并代价达到最小。
输入描述 Input Description
第一行一个整数 n(n<=100)
第二行 n 个整数 w1,w2...wn (wi <= 100)
输出描述 Output Description
一个整数表示最小合并代价
样例输入 Sample Input
4
4 1 1 4
样例输出 Sample Output
18
数据范围及提示 Data Size & Hint
分类标签 Tags 点此展开
- #include
- #include
- #include
- using namespace std;
- intdp[210][210],sum[210][210],a[210],f[210][210];
- int n;
- int main (){
- while(~scanf("%d",&n)){
- // memset(dp,MAX,sizeof(dp));
- for(inti=1;i<=n;i++)
- scanf("%d",&a[i]);
- for(inti=1;i<=n;i++){
- dp[i][i]=0;//初始化为0sum[i][i]=a[i];//将每堆石子的个数赋值进来
- }
- for(inti=1;i<=n;i++)
- for(intj=1;j<=n;j++)
- if(i==j) f[i][j]=0;
- elsef[i][j]=0x7fffffff;
- for(intlen=1;len//按长度从小到大枚举
- for(inti=1;i<=n&&i+len<=n;i++){//i表示开始位置
- intj=len+i;//j表示长度为len的一段区间的结束位置
- for(intk=i;k//用k来表示分割区间sum[i][j]=sum[i][k]+sum[k+1][j];
- dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+sum[i][j]);
- f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum[i][j]);
- }
- }
- }
- cout<1][n]<<endl;
- //cout<<dp[1][n]<<endl;
- }
- return 0;
- }
1048 石子归并 codevs
来源: http://www.bubuko.com/infodetail-2035170.html