cdoj 1131 男神的礼物 区间dp

男神的礼物

Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://acm.uestc.edu.cn/#/problem/show/1131

Description

Lweb学长是集训队里公认的男神。有一天他要给美美的学姐姐准备礼物。

Lweb学长可是会魔法的哟。为了准备一份礼物，男神要加工n份材料。每一次只能加工相邻的材料。

当男神加工两个魔法值为a,b的材料，男神都要消耗a*b的体力，同时在这个地方合成出魔法值(a+b)0的材料。

男神为了能节省体力来完成他的礼物。想找聪明的你帮他算一算他所要花费的最小体力。

Input

第一行一个整数T，表示男神所要准备的礼物数。 之后的T组数据各有两行数据，第一行有一个整数n，表示这份礼物的材料数(1<=n<=100)。 接下来一行有n个整数a(0<=a<100)，表示这件礼物第i份材料的魔法值。

Output

每组数据一行输出，表示男神制作这份礼物所要的最小体力。

Sample Input

2
2
18 19
3
40 60 20

Sample Output

342
2400

HINT

对于样例 2：

先加工材料40和60，得到0的材料，消耗40∗60体力，共消耗2400体力；

再加工材料0和20，得到20的材料，消耗0∗20体力，共消耗2400体力.

题意

题解：

区间dp，类似于石子合并的问题，每次每枚举合并的点就好了

代码：

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 200001

#define mod 10007

#define eps 1e-9

int Num;

char CH[];

const int inf=0x7fffffff;   //нчоч╢С

/*

inline void P(int x)

{

    Num=0;if(!x){putchar('0');puts("");return;}

    while(x>0)CH[++Num]=x%10,x/=10;

    while(Num)putchar(CH[Num--]+48);

    puts("");

}

*/

inline ll read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline void P(int x)

{

    Num=;if(!x){putchar('');puts("");return;}

    while(x>)CH[++Num]=x%,x/=;

    while(Num)putchar(CH[Num--]+);

    puts("");

}

//**************************************************************************************

ll dp[][];

ll a[];

ll sum[];

int main()

{

    int t=read();

    while(t--)

    {

        memset(dp,,sizeof(dp));

        memset(sum,,sizeof(sum));

        int n=read();

        for(int i=;i<=n;i++)

        {

            a[i]=read();

            sum[i]=a[i]+sum[i-];

        }

        for(int r=;r<=n;r++)

        {

             for(int i=r-;i>=;i--)

            {

                for(int j=i;j<=r;j++)

                {

                    ll kiss=((sum[j]-sum[i-])%)*((sum[r]-sum[j])%);

                    if(dp[i][r]==)

                        dp[i][r]=dp[i][j]+dp[j+][r]+kiss;

                    else

                        dp[i][r]=min(dp[i][r],dp[i][j]+dp[j+][r]+kiss);

                }

            }

        }

        cout<<dp[][n]<<endl;

    }

}