线性DP P1269

见注释

注意理解sum表示含义以及f[i][j]和sum联系

#include<cstdio>

#include<algorithm>

#include<cstring>

#define F(i,s,e) for(int i=s;i<=e;i++)

#define D(i,e,s) for(int i=e;i>=s;i--)

using namespace std;

int n,m;

int f[520][520];//zzh beser

int sum[520][520];

int h[520],temp;...

P1269

见注释

注意理解sum表示含义以及f[i][j]和sum联系

#include<cstdio>

#include<algorithm>

#include<cstring>

#define F(i,s,e) for(int i=s;i<=e;i++)

#define D(i,e,s) for(int i=e;i>=s;i--)

using namespace std;

int n,m;

int f[520][520];//zzh beser

int sum[520][520];

int h[520],temp;

int main()

{

    scanf("%d%d",&n,&m);

    F(i,1,n)

        scanf("%d",&h[i]);

    memset(f,10000,sizeof(f));

    F(i,1,n)//求任意i~j区间内的不和谐度

    {

        F(j,i,n)

        {

            temp=0;

            F(k,i,j)

                temp+=h[k];

            sum[i][j]=temp*(j-i+1-temp);

        }

        f[1][i]=sum[1][i];//到i的不和谐度就是1~i不和谐度

    }

    F(i,2,m)

        F(j,i,n)

            F(k,i-1,j)

                f[i][j]=min(f[i][j],f[i-1][k]+sum[k+1][j]);

    printf("%d\n",f[m][n]); 

    return 0;

}