// [解题方法]
// 将筷子按长度从大到小排序
// 排序原因:
// 由于一组中A<=B<=C
// 选第i根筷子作为A时,必然要选第i-1根作为B,否则不会达到最优
// dp[i][j]表示选了对于前j根筷子选了i个筷子集合时的最小花费
// 设c[j]为选j作为A,j-1作为B时的花费(c[j]=(w[i]-w[i-1])^2;),状态转移如下:
// dp[i][j] = min( dp[i-1][j-2]+c[j](j>=3*i), dp[i][j-1](j>=3*i+1) );
// 要j和j-1作为AB形成新的筷子组 不要j作为A形成新筷子组
// 由于还有C,C>=B>=A,所以j被限制了范围,所以对于dp[i][j]:
// 形成i个筷子组中最后一组的A最低只能在3*i形成,所以确定了j的范围
// 注:这里用了滚动数组优化空间
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
#define LL long long
#define N 1005
#define M 5005
#define inf 0x3fffffff
LL dp[M], w[M], c[M];
int main()
{
int t, i, j, n, k;
cin >> t;
while (t--)
{
cin >> k >> n;
k += 8;
for (i = n; i >= 1; i--)
cin >> w[i];
for (i = 2; i <= n; i++)
c[i] = (w[i]-w[i-1])*(w[i]-w[i-1]);
memset (dp, 0, sizeof(dp));
for (i = 1; i <= k; i++)
{
int m = 3*i;
for (j = n; j >= m; j--)
dp[j] = dp[j-2]+c[j];
for (j = m+1; j <= n; j++)
if (dp[j-1] < dp[j])
dp[j] = dp[j-1];
}
cout << dp[n] << endl;
}
return 0;
}
分享到:
相关推荐
Chopsticks是一个orchestration 库,可以通过SSH远程管理和配置主机。Chopsticks对标的项目是fabric和ansible,不同的是,它不是把命令最终发给bash,而是让你在一个类似Python终端的环境中操作。它也支持Docker。
杭州ACM-Chopsticks解题
英语作业4-Fan chopsticks.doc
Chopsticks1
chopsticks是用于日常使用的Scala库的重要集合。 它是专门为构建高性能,生产级功能性React流系统而设计的。 这些已在我们的内部生产流系统中得到广泛使用,多年来,处理持久性写入次数超过一百万次/秒,而每台...
筷子手游戏JS 关于 从未听说过筷子游戏吗? 这是一个简单的基于回合的手形游戏,其中两个玩家从手到手转移点(如伸出的手指数所示)。 游戏规则 游戏以每手一分开始,当玩家输掉所有分后结束游戏。...
外研一起小学英语五下《Module9Unit 2 Mum bought new chopsticks for you.》word教案.docx
筷子(游戏)探索 具有作为依赖项。 此应用程序计算表示筷子游戏可能状态之间的联系的图形。 每个状态都通过几种可能的动作与其他状态相关联,这些动作包括: 以轮到该玩家的一只手的手指数,并将其添加到另一...
筷子 1,基于Java8的快速入门Web框架 2,使用Netty,不依赖JavaEE,所以不能使用servlet,jsp,部署也不需要tomcat 3,ioc,mvc参考弹簧的实现 4,内置JSON输出
寿司卷 :sushi: 字节大小的与寿司金融互动的方式 :chopsticks:
chopsticks the missing android layouter. It is sometimes a pain to layout your views programmatically using Java codes. The Java API cannot be used as the same way as XML. Chopsticks is the rescue. ...
Chopsticks 类:设置筷子的各种参数和使用方法,例如是否被使用,设置筷子的状态 Philosopher 类:设置哲学家的思考、等待和吃饭方法。 详细介绍参考:...
餐饮_哲学家_问题在计算机科学中,进餐哲学家问题是并发算法设计中经常使用的一个示例问题,用于说明同步问题和解决这些问题的技术。 它最初是由Edsger Dijkstra于1965年制定的,它是一项学生考试练习,以计算机竞争...
:chopsticks: 通过Apigateway创建端点。 从serverless.yml创建资源。 连接到现有资源dynamodb 。 简要介绍graphql端点和lambda。 我们建造了什么 免责声明 :bowl_with_spoon: 使用它需要您自担风险,我创建了...
Rax是用于构建通用应用程序的渐...快速开始 :chopsticks: :cooked_rice: 从命令行开始 使用create-rax创建一个新的Rax项目: $ npm init rax npm init 在npm 6+中可用 启动本地服务器以启动项目: $ cd < YourP
快速入门 :chopsticks: :cooked_rice: 从命令行开始使用 create-rax 创建一个新的 Rax 项目: $ npm init rax 初始化 在 npm 6+ 中可用启动本地服务器来启动项目:$ cd $ npm install $ npm run start 从 VS Code ...
ZJU_Main 主页 下一页 ZJU 题型分类 文演整理版 2008-3-23 数论: 1007 Numerical Summation of a Series 简单题,还是蛮有意思的 1045 HangOver 简单题 ... 1049 I Think I Need a Houseboat 简单题 ...
ZJU 题型分类 ZJU_Main 主页 下一页 ZJU 题型分类 文演整理版 2008-3-23 数论: 1007 Numerical Summation of a Series 简单题,还是蛮有意思的 ... 1049 I Think I Need a Houseboat 简单题 ...