动归经典

例9.18    合并石子。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
int f[101][101],s[101];
int main()
{
    memset(f,127/3,sizeof(f));
    int n,x;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        s[i]=s[i-1]+x;
    }
    for(int i=1;i<=n;i++) f[i][i]=0;
    for(int i=n-1;i>=1;i--)
    for(int j=i+1;j<=n;j++)
    for(int k=i;k<=j-1;k++)
    f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
    cout<<f[1][n]<<endl<<endl;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
        cout<<f[i][j]<<' ';
    cout<<endl;
    }
    return 0;
}

如果初始化为0，则数组全为0，无法正常的值。而只初始化为127/3（一个相当大的值，memset只能正常给数组赋值0、-1，）不初始化f[i][i]=0，也只能得到不正确的值。

图为未初始化f[i][i]=0，正常输出，以及数组值。