Chopsticks
2024-08-27 05:13:23
题意:
n个数3个相邻是一组,求选k组使得,各组组内较小的两个数的差之和最小。
分析:
对于每个数选或不选的问题,dp[i][j]表前i个数选了j组得到的最小和。
dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+差)选或不选,数应该降序排列。
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <complex>
#include <cassert>
#include <utility>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
#define lson l,m,rt<<1
#define pi acos(-1.0)
#define rson m+1,r,rt<<11
#define All 1,N,1
#define read freopen("in.txt", "r", stdin)
const ll INFll = 0x3f3f3f3f3f3f3f3fLL;
const int INF= 0x7ffffff;
const int mod = ;
int dp[][];
int l[];
int n,k;
void solve(){
for(int i=;i<=n;++i){
dp[i][]=;
for(int j=;j<=k;++j)
dp[i][j]=INF;
}
for(int i=;i<=n;++i)
for(int j=;j<=k;++j)
if(i>=*j&&dp[i-][j-]!=INF){
dp[i][j]=min(dp[i-][j],dp[i-][j-]+(l[i]-l[i-])*(l[i]-l[i-]));
}
printf("%d\n",dp[n][k]);
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&k,&n);
for(int i=n;i>;--i)
scanf("%d",&l[i]);
k+=;
solve();
}
return ;
}
最新文章
- GJM : 各大开发游戏引擎
- 将已有项目提交到github/从github上pull到本地
- 接触Matlab10年后的一个总结,随时使用Matlab要掌握的一些要点
- 1.4 基础知识——GP2.2 计划 与 GP2.8 计划跟踪
- jquery 生成table表格 部分代码
- nyoj221_Tree_subsequent_traversal
- js鼠标滑轮滚动事件绑定(兼容主流浏览器)
- Dinic问题
- POJ 1988 Cube Stacking
- gcc和arm-linux-gcc 头文件寻找路径【转】
- win2003 安装itunes ----iphone4s
- File System Minifilter Drivers(文件系统微型过滤驱动)入门
- Android 中Java和JavaScript交互入门
- Markdown编辑器 简单使用
- 开博近一年的感想 by 程序员小白
- html的分类与特点
- 创建一个vue项目()
- validationEngine 使用
- kafka各个版本特点介绍和总结
- Python Web学习笔记之IGMP和ICMP的差别
热门文章
- React组件生命周期-正确执行初始化阶段的函数
- 对话框上右下角显示resize icon(可以拖动改变对话框的大小)(在WM_CREATE的时候,增加WS_THICKFRAME风格)
- iOS Architecture
- AdventureWorksDW2008R2 attach: Unable to open the physical file. Operating system error 5: ";5(Access is denied.)
- makefile中的自动化变量 【转】
- spring3定时器简单配置
- laravel Event执行顺序
- github创建repo,本地导入git项目到github
- SVG 动画实现弹性的页面元素效果
- svn备份脚 本