SP345 Mixtures – 划水



题目链接:SP345


Description
哈利·波特在他面前有n个混合物,排列成一排。每种混合物都有100种不同颜色之一(颜色的数字从0到99)。

他想把所有这些混合物混合在一起。在每个步骤中,他将采取两个彼此相邻的混合物并将它们混合在一起,并将所得到的混合物置于其中。

当混合两种颜色a和b的混合物时,得到的混合物将具有颜色(a+b)mod 100

而且,在这个过程中会有一些烟雾。当混合两种颜色a和b的混合物时产生的烟雾的量是ab

找出混合所有混合物时Harry能得到的最小烟雾量。


Input
输入中会有一些测试用例。
每个测试用例的第一行将包含n,即混合物的数量,1<=n<=100。
第二行将包含0到99之间的n个整数 — 混合物的初始颜色。


Output
对于每个测试案例,输出最小量的烟雾。


Sample Input 1
2
18 19
3
40 60 20


Sample Output 1
342
2400


Solution
真的水题….
就是环型石子合并……把贡献由和改成积就OK


Code

#include<map>
#include<set>
#include<list>
#include<queue>
#include<vector>
#include<string>
#include<time.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
//#define Judge
//#define Online
#define reg register
#define ll long long
#define mod 1000000007
#define inf 2147483647
#define lowbit(x) ((x)&-(x))
#define abs(x) ((x)<0?-(x):(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define ckmax(a,b) ((a)=max((a),(b)))
#define ckmin(a,b) ((a)=min((a),(b)))
using namespace std;
#ifdef Judge
#define puts io.put
#define getchar io.gc
#define putchar io.wchar
#ifdef Online
FILE*in=stdin;
FILE*out=stdout;
#else
FILE*in=fopen(".in","r+");
FILE*out=fopen(".out","w+");
#endif
struct FastIO{
    #define S 1000000
    int wpos,len,pos;char wbuf[S],buf[S];
    FastIO(){wpos=0,len=0,pos=0;}
    inline char gc(){
        if (pos==len) pos=0,len=fread(buf,1,S,in);
        if (pos==len) return 0; return buf[pos++];
    }
    inline void wchar(int x) {
        if (wpos==S) fwrite(wbuf,1,S,out),wpos=0;
        wbuf[wpos++]=x;
    }
    inline void put(const char*s) {for(; *s; ) wchar(*s++);}
    ~FastIO() {
        if (wpos) fwrite(wbuf,1,wpos,out),wpos=0;
    }
}io;
#endif
template<typename T> inline void read(T&x){T f=1;x=0;char c;
    for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
    for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c=0){char ch[(sizeof(T)+1)<<1];if (x<0) x=-x,putchar('-');
    int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!=0) putchar(c);
}
int f[101][101],d[101],n;
int main(int argv,char*argc[]){
    while(scanf("%d",&n)==1){
        memset(d,0,sizeof d),memset(f,0,sizeof f);
        for (int i=1; i<=n; ++i) read(d[i]),d[i]+=d[i-1];
        for (int k=2; k<=n; ++k) for (int i=1,g=n-k+1; i<=g; ++i){
            int j=i+k-1;f[i][j]=inf;  for (int p=i; p<j; ++p)
                f[i][j]=min(f[i][j],f[i][p]+f[p+1][j]+((d[p]-d[i-1])%100)*((d[j]-d[p])%100));
        }
        wt(f[1][n],'\n');
    }
    return 0;
}



点我回到主页

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google photo

You are commenting using your Google account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s