Des丨tiny丶柠凉

蓦然回首,前尘不堪流连,自卿离去,暗淡了这俗世繁华,只余孤影几度徘徊,独酌月下,对影成殇;

时间留不住记忆的海,不过是黯然神伤,默默着无奈。


book解题报告

问题描述

暑假到了,Rick制定了一个长达M天的阅读计划。他一共有N本书,从1至N进行标号;Rick将它们从上至下摞成一堆。他每天都会读一本书,假设他要读编号为X的书,他会按照以下步骤:
1,将这本书上方的所有书搬起来。
2,将这本书拿出来
3,将搬起来的书挪回去。
4,看完后把这本书放到顶端。

每本书都会有各自的重量,Rick不希望搬起太过重的书。于是他希望能重新安排这N本书的顺序,使得读完M本书之后,搬书的重量之和最小。


输入格式

第一行两个整数M和N,分别表示书的数量和阅读的天数。
第二行N个整数,表示每本书的重量。
第三行M个整数,表示每天要读的书的编号。


输出格式

一行一个整数,表示最小的重量之和。

数据范围与约束

对于30%的数据,N<=10.

对于100%的数据,2<=N<=500, 1<=M<=1000,
每本书重量不超过100.


解题思路

如果只读一本书,那直接放在最上面的位置;
如果读两本书,考虑第一本书,无论怎样第一天后他都会放到顶上,不如直接就放在顶上。
假如我只读三本书,类似,在读完前两本书后,他们肯定会放在最上方,所以放到第三位置是最优的。(如果往上放,还会给之前的其他书增加重量)
所以采取贪心的策略:按阅读顺序从上往下放。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<queue>
#include<deque>
#include<stack>
#include<vector>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n,m,a[1005],book[505],w[505],ans,cnt;
bool have[505];
int main(){
freopen("book.in","r",stdin);
freopen("book.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++)
scanf("%d",&w[i]);
for(int i = 1;i <= m;i++){
scanf("%d",&a[i]);
if(!have[a[i]]){
have[a[i]] = true;
book[++cnt] = a[i];
}
}
for(int i = 1;i <= m;i++){
int num;
for(int j = 1;j <= cnt;j++){
if(book[j] == a[i]){
num = j;
break;
}
ans += w[book[j]];
}
for(int j = num;j >= 2;j--)
book[j] = book[j-1];
book[1] = a[i];
}
cout<< ans;
return 0;
}
最近的文章

codevs伊吹萃香

题目链接题目描述 在幻想乡,伊吹萃香是能够控制物体密度的鬼王。因为能够控制密度,所以萃香能够制造白洞和黑洞,并可以随时改变它们。某一天萃香闲着无聊,在妖怪之山上设置了一些白洞或黑洞,由于引力的影响,给妖怪们带来了很大的麻烦。于是他们决定找出一条消耗体力最少的路,来方便进出。已知妖怪之山上有N个路口( …

于  最短路 继续阅读
更早的文章

cyclic解题报告

题目描述 给出一个字符串S与N个操作。每个操作用三元组(L, R, K)进行描述:操作将字符串第L个到第R个位置构成的子串循环移动K次。一次循环移动就是将字符串最后的这个字符移动到第一位,其余的字符顺次后移。 例如,对于字符串abacaba,操作(L=3, R=6, K=1)后得到的字符串即为abb …

于  STL, 字符串 继续阅读