制作门户网站,网站开发的意义和作用,外贸网站推广销售,做暧暧视频网站w男神的礼物 Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://acm.uestc.edu.cn/#/problem/show/1131 Description Lweb学长是集训队里公认的男神。有一天他要给美美的学姐姐准备礼物。Lweb学长可是会魔法的哟。为了准备一份礼物#xff0c;男神要加工n份材料。每一次…男神的礼物 Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://acm.uestc.edu.cn/#/problem/show/1131 Description Lweb学长是集训队里公认的男神。有一天他要给美美的学姐姐准备礼物。Lweb学长可是会魔法的哟。为了准备一份礼物男神要加工n份材料。每一次只能加工相邻的材料。当男神加工两个魔法值为a,b的材料男神都要消耗a*b的体力同时在这个地方合成出魔法值(ab)0的材料。男神为了能节省体力来完成他的礼物。想找聪明的你帮他算一算他所要花费的最小体力。 Input 第一行一个整数T表示男神所要准备的礼物数。 之后的T组数据各有两行数据第一行有一个整数n表示这份礼物的材料数(1n100)。 接下来一行有n个整数a(0a100)表示这件礼物第i份材料的魔法值。 Output 每组数据一行输出表示男神制作这份礼物所要的最小体力。 Sample Input 2218 19340 60 20 Sample Output 3422400 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[20];
const int inf0x7fffffff; //нчоч╢С
/*inline void P(int x)
{Num0;if(!x){putchar(0);puts();return;}while(x0)CH[Num]x%10,x/10;while(Num)putchar(CH[Num--]48);puts();
}
*/
inline ll read()
{int x0,f1;char chgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9){xx*10ch-0;chgetchar();}return x*f;
}
inline void P(int x)
{Num0;if(!x){putchar(0);puts();return;}while(x0)CH[Num]x%10,x/10;while(Num)putchar(CH[Num--]48);puts();
}
//**************************************************************************************ll dp[101][101];
ll a[101];
ll sum[101];
int main()
{int tread();while(t--){memset(dp,0,sizeof(dp));memset(sum,0,sizeof(sum));int nread();for(int i1;in;i){a[i]read();sum[i]a[i]sum[i-1];}for(int r2;rn;r){for(int ir-1;i1;i--){for(int ji;jr;j){ll kiss((sum[j]-sum[i-1])%100)*((sum[r]-sum[j])%100);if(dp[i][r]0)dp[i][r]dp[i][j]dp[j1][r]kiss;elsedp[i][r]min(dp[i][r],dp[i][j]dp[j1][r]kiss);}}}coutdp[1][n]endl;}
}
