洛谷p1103书本整理（动规）

关键词：

洛谷 P1103 书本整理

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cstdio>
 6 using namespace std;
 7 struct bo{
 8     int a,b;
 9 }s[105];
10 int comp(const bo& x,const bo& y)
11 {
12     if(x.a<y.a)
13         return 1;
14     return 0;
15     }
16 int n,k,f[105][105],a[105][105],minn=1000000;
17 int main(){
18         cin>>n>>k;
19         for(int i=1;i<=n;i++)
20             cin>>s[i].a>>s[i].b;
21         sort(s+1,s+1+n,comp);
22         
23         for(int i=1;i<=n;i++)
24                 f[i][1]=0;
25         for(int i=1;i<=n;i++)
26             for(int j=2;j<=min(i,n-k);j++)
27             {f[i][j]=100000000;
28                 
29                 for(int x=j-1;x<=i-1;x++)
30                 {
31                     f[i][j]=min(f[i][j],f[x][j-1]+abs(s[i].b-s[x].b));
32                     }}
33                     for(int i=n-k;i<=n;i++)
34                     {minn=min(minn,f[i][n-k]);
35                     }
36                     cout<<minn;
37         }

动态规划洛谷p1103书本整理

P1103书本整理题目描述Frank是一个非常喜爱整洁的人。他有一大堆书和一个书架，想要把书放在书架上。书架可以放下所有的书，所以Frank首先将书按高度顺序排列在书架上。但是Frank发现，由于很多书的宽度不同，所以书看起来... 查看详情

p1103书本整理

P1103书本整理题目描述Frank是一个非常喜爱整洁的人。他有一大堆书和一个书架，想要把书放在书架上。书架可以放下所有的书，所以Frank首先将书按高度顺序排列在书架上。但是Frank发现，由于很多书的宽度不同，所以书看起来... 查看详情

p1103书本整理（dp）

ReactHookHook是React16.8的新增特性，它可以让你在不使用class的情况下，使用state以及其他的React特性。React16.8.0是第一个支持Hook的版本。注意：Hook是完全可选的、100%向后兼容，Hook和现有代码可以同时工作。Hook不能在class组件中使... 查看详情

p1103书本整理

题目描述Frank是一个非常喜爱整洁的人。他有一大堆书和一个书架，想要把书放在书架上。书架可以放下所有的书，所以Frank首先将书按高度顺序排列在书架上。但是Frank发现，由于很多书的宽度不同，所以书看起来还是非常不整... 查看详情

p1103书本整理(代码片段)

题目描述Frank是一个非常喜爱整洁的人。他有一大堆书和一个书架，想要把书放在书架上。书架可以放下所有的书，所以Frank首先将书按高度顺序排列在书架上。但是Frank发现，由于很多书的宽度不同，所以书看起来还是非常不整... 查看详情

p1103书本整理(代码片段)

题意：给出n本书每本书有高度和宽度，题意让我们先讲高度排序(保证每一本书的高度不同，从大从小排对答案不影响)　　　　　相邻的书的宽度差的绝对值为贡献，让我们去掉其中k本书，求最小贡献思路：去掉书的想法很难... 查看详情

洛谷p1352——动规

题目：https://www.luogu.org/problemnew/show/P1352代码如下：#include<iostream>#include<cstdio>usingnamespacestd;intn,r[6005],cnt[6005],f[6005][3],ct,ans;boolvis[6005];structN{ intto,next;}edge[6005 查看详情

洛谷p2986[usaco10mar]伟大的奶牛聚集（树形动规）

题目描述BessieisplanningtheannualGreatCowGatheringforcowsallacrossthecountryand,ofcourse,shewouldliketochoosethemostconvenientlocationforthegatheringtotakeplace.Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然， 查看详情

题解整理书本(代码片段)

题目描述　　小A想把他满屋子的书整理一下。书本分成若干堆。每一堆的书本都有质量w和价值v。小A的任务是将所有书合成一堆。因为小A认为合并i，j两堆的书所需要的力为w[i]-v[i]+w[j]-v[j]。合并后的书堆的质量和价值均为合并... 查看详情

luogup1103书本整理の心得

传送门qwq　　卡了好长时间，结果发现是一道普及的题，啪啪啪啪啪。。。。。　　虽然dp方程不难想，但是思路还是很重要的，**转化题意**是最重要的一步，例如，抽调k本书，可以转化为在n本书里选择n-k本书，而不是去写sb... 查看详情

[luogup1103]书本整理（dp）

传送门 以去掉多少个为阶段不好做。去掉k个也可以变成选n-k个f[i][j]表示前i个数中选j个的最优解，a[i]必选f[i][j]=min(f[i][j],f[k][j-1]+abs(b[k]-b[i]))(2<=j<=min(i,n-m),j-1<=k<i) ——代码1#include<cstdio>2#inclu 查看详情

ride创建工程和测试套件和用例--书本介绍的入门方法，自己整理实践下

1.选择File->NewProject2.弹出的NewProject对话框，在Name文本框输入一个名词，如“TestProject-0805”,右侧选中“Directory”,选中建立的是一个工程文件夹。3.点击OK，结果如下图：4.右键单击“TestProject-0805”，弹出菜单选择“NewSuite”5.弹... 查看详情

算法训练p1103

水，注意好输入输出就可以#include<iostream>#include<iomanip>usingnamespacestd;voidjia(doublex,doubley,doublez,doublew){cout<<fixed<<setprecision(2)<<x+z<<‘+‘<<y+w<<‘ 查看详情

洛谷_递归整理

P1427 小鱼的数字游戏 题目描述小鱼最近被要求参加一个数字游戏，要求它把看到的一串数字（长度不一定，以0结束，最多不超过100个，数字不超过2^32-1），记住了然后反着念出来(表示结束的数字0就不要念出来了)。这对... 查看详情

洛谷p2904[usaco08mar]跨河rivercrossing(代码片段)

题目动规方程f[i]=min(f[i],f[i?j]+sum)我们默认为新加一头牛，自占一条船。想象一下，它不断招呼前面的牛，邀请它们坐自己这条船，当且仅当所需总时间更短时，前一头奶牛会接受邀请，最多邀请前面的所有奶牛一起坐这条船。1#... 查看详情

动规(22)-并查集基础题——cd收藏cd.cpp（并查集）(代码片段)

...爱听歌，所以买了很多的CD来收藏，但是因为平常整理不当，所以忘记了这些CD的歌手是谁。现在他想知道他到底收藏了多少位歌手的专辑，于是他想了一个办法，同时拿出两个CD来听，可以分辨出来是否为... 查看详情

动规(22)-并查集基础题——cd收藏cd.cpp（并查集）(代码片段)

...爱听歌，所以买了很多的CD来收藏，但是因为平常整理不当，所以忘记了这些CD的歌手是谁。现在他想知道他到底收藏了多少位歌手的专辑，于是他想了一个办法，同时拿出两个CD来听，可以分辨出来是否为... 查看详情

动规(22)-并查集基础题——cd收藏cd.cpp（并查集）(代码片段)

...爱听歌，所以买了很多的CD来收藏，但是因为平常整理不当，所以忘记了这些CD的歌手是谁。现在他想知道他到底收藏了多少位歌手的专辑，于是他想了一个办法，同时拿出两个CD来听，可以分辨出来是否为... 查看详情