FZU2177——ytaaa——————【区间dp】

时间:2022-08-26 10:23:16
 ytaaa

Time Limit:2000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

Description

Ytaaa作为一名特工执行了无数困难的任务,这一次ytaaa收到命令,需要炸毁敌人的一个工厂,为此ytaaa需要制造一批炸弹以供使用。 Ytaaa使用的这种新型炸弹由若干个炸药组成,每个炸药都有它的威力值,而炸弹的威力值为组成这个炸弹的所有炸药的最大威力差的平方,即(max-min)^2,假设一个炸弹有5个炸药组成,威力分别为5 9 8 2 1,那么它的威力为(9-1)^2=64。现在在炸弹的制造流水线上已经有一行n个炸药,由于时间紧迫,ytaaa并没有时间改变它们的顺序,只能确定他们的分组。作为ytaaa的首席顾问,请你帮助ytaaa确定炸药的分组,使制造出的炸弹拥有最大的威力和。

Input

输入由多组数据组成。第一行为一个正整数n(n<=1000),第二行为n个数,第i个数a[i]为第i个炸药的威力值(0<=a[i]<=1000)。

Output

对于给定的输入,输出一行一个数,为所有炸弹的最大威力和。

Sample Input

6 5 9 8 2 1 6

Sample Output

77
 
 
定义状态:dp[i]表示前i个炸药能组成的最大威力和。状态转移方程:dp[i]=max(dp[i],dp[j-1]+(a[i]-a[j])^2)
 
 
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=1100;
int dp[maxn];
int a[maxn];
int main(){ int n;
while(scanf("%d",&n)!=EOF){ for(int i=1;i<=n;i++){ scanf("%d",&a[i]);
}
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++){ for(int j=i;j>=1;j--){ dp[i]=max(dp[i],dp[j-1]+(a[i]-a[j])*(a[i]-a[j]));
}
}
printf("%d\n",dp[n]); }
return 0;
}

  

FZU2177——ytaaa——————【区间dp】的更多相关文章

  1. 【BZOJ-4380】Myjnie 区间DP

    4380: [POI2015]Myjnie Time Limit: 40 Sec  Memory Limit: 256 MBSec  Special JudgeSubmit: 162  Solved: ...

  2. 【POJ-1390】Blocks 区间DP

    Blocks Time Limit: 5000MS   Memory Limit: 65536K Total Submissions: 5252   Accepted: 2165 Descriptio ...

  3. 区间DP LightOJ 1422 Halloween Costumes

    http://lightoj.com/volume_showproblem.php?problem=1422 做的第一道区间DP的题目,试水. 参考解题报告: http://www.cnblogs.c ...

  4. BZOJ1055&colon; &lbrack;HAOI2008&rsqb;玩具取名&lbrack;区间DP&rsqb;

    1055: [HAOI2008]玩具取名 Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 1588  Solved: 925[Submit][Statu ...

  5. poj2955 Brackets &lpar;区间dp&rpar;

    题目链接:http://poj.org/problem?id=2955 题意:给定字符串 求括号匹配最多时的子串长度. 区间dp,状态转移方程: dp[i][j]=max ( dp[i][j] , 2 ...

  6. HDU5900 QSC and Master(区间DP &plus; 最小费用最大流)

    题目 Source http://acm.hdu.edu.cn/showproblem.php?pid=5900 Description Every school has some legends, ...

  7. BZOJ 1260&amp&semi;UVa 4394 区间DP

    题意: 给一段字符串成段染色,问染成目标串最少次数. SOL: 区间DP... DP[i][j]表示从i染到j最小代价 转移:dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k ...

  8. 区间dp总结篇

    前言:这两天没有写什么题目,把前两周做的有些意思的背包题和最长递增.公共子序列写了个总结.反过去写总结,总能让自己有一番收获......就区间dp来说,一开始我完全不明白它是怎么应用的,甚至于看解题报 ...

  9. Uva 10891 经典博弈区间DP

    经典博弈区间DP 题目链接:https://uva.onlinejudge.org/external/108/p10891.pdf 题意: 给定n个数字,A和B可以从这串数字的两端任意选数字,一次只能 ...

  10. 2016 年沈阳网络赛---QSC and Master&lpar;区间DP&rpar;

    题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=5900 Problem Description Every school has some legend ...

随机推荐

  1. Qt中使用Windows API

    在Windows平台上进行开发,不可避免与Windows API打交道,Qt中使用的时候要添加对应API的头文件和链接lib文件,另外使用的Windows API的代码部分要使用#ifdef  Q_O ...

  2. WCF 部署在Windows 2012 IIS上各种报错的解决方法

    1.由于扩展配置问题而无法提供您请求的页面.如果该页面是脚本 ,请添加处理程序.如果勇载文件,请添加 MIME 映射. 以管理员身份,在cmd中运行C:\Windows\Microsoft.NET\F ...

  3. &lbrack;Ubuntu&rsqb; bash&colon; warning&colon; setlocale&colon; LC&lowbar;ALL&colon; cannot change locale

    问题症状 -bash: warning: setlocale: LC_ALL: cannot change locale (en_US.utf8) 解决方法 本地化是指不同地区用户在键盘上输入不同语言 ...

  4. 【WPF】无边框窗体

    之前写了一个支持尺寸变换的无边框窗体的一个基窗体,代码如下: public class LBaseWindow : Window { /// <summary> /// 基窗体 /// & ...

  5. &lpar;转&rpar;mysql的增删改查

    MySQL数据库的增删改查. 1,首先启动mysql数据库的服务,在运行的窗口中输入:net start mysql,这样,就可 以启动mysql数据库的服务,同理,输入net stop mysql, ...

  6. RPI学习--环境搭建&lowbar;更新firmware

    (用以解决USB摄像头不识别的状况) rpi-update是老外开发的一个更新树莓派firmware的工具 $ sudo apt-get update  $ sudo apt-get install ...

  7. JavaBean 和 Map 之间互相转换

    JavaBean 和 Map 之间互相转换 import java.beans.BeanInfo; import java.beans.IntrospectionException; import j ...

  8. IOS开发基础

    http://blog.csdn.net/wokenshin/article/details/50292253 1.修改UI大小 2.设置颜色 3.禁止横屏 4.点击空白处隐藏键盘 5.弹出键盘时,后 ...

  9. (诊断)为GitHub添加SSH key时出现&OpenCurlyDoubleQuote;Could not open a connection to your authentication agent”错误的应对方案(转)

    在为windows 环境下的github账户添加SSH key时,需要在Git Bash执行如下命令: 第一步:检查已有的SSH keys $ ls -al ~/.ssh 第二步:生成新的SSH ke ...

  10. Layout Renderers

    Layout Renderers NLog package ${activityid} - Puts into log a System.Diagnostics trace correlation i ...