第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（昆明）(热身赛)

A. Meditation 模拟

链接：https://ac.nowcoder.com/acm/contest/13977/A
来源：牛客网

Luna had a stressful day and she wants to do a meditation routine that relaxes her well. Luna’s routines are more or less relaxing and to determine how relaxing a routine is, Luna computes its score: the higher the score, the more relaxing it is!
Luna has graded each of the nn exercises with a positive integer and the score of a routine is simply the sum of the grades of its individual exercises. She gives you her list of graded exercises and asks you what is the maximal grade of a routine composed of kk different exercises.
输入描述:
The first line of the input contains two space-separated integers:nn and kk.
The nn following lines each contain a single integer, the i+1-thi+1−th line containing the grade g_ig
i
​
of the ii-th exercise.
输出描述:
The output should contain a single line with a single integer: the maximal score of a routine composed of KK different exercises.
示例1
输入
复制
5 3
10
22
7
3
10
输出
复制
42
说明
We select the exercises 1, 2 and 5 which gives a total score of 10+22+10=4210+22+10=42.
备注:
1\leq k \leq n \leq 100,0001≤k≤n≤100000
0\leq g_{i}\leq 10,0000≤g
i
​
≤10000

• 找出最大的k个数加起来

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int a[maxn];
bool cmp(int x, int y){
	return x>y;
}
int main(){
	int n, k;
	cin>>n>>k;
	for(int i = 1; i <= n; i++)cin>>a[i];
	sort(a+1,a+n+1,cmp);
	int ans = 0;
	for(int i = 1; i <= k; i++){
		ans += a[i];
	}
	cout<<ans<<"\n";
	return 0;
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
 

B. Rounds 数学

链接：https://ac.nowcoder.com/acm/contest/13977/B
来源：牛客网

The popular PefectSharp online group gathers fans of workouts and healthy lifestyle all over the world. Every group member has managed to gain a certain amount of credits for the trendy MV03 online sports platform, giving them access to various workout and relaxation resources.
The amount of credits owned may however largely differ from one person to the other. Since PefectSharp  members value sharing and solidarity, they decide to redispatch credits by playing the following game:
The N group members are numbered from 1 to N and the game comprises k rounds, for some integer k such that  1 \leq k \leq N1≤k≤N. During the i-th round of the game, all members except member i give S credits to member i. The game may end after any round, and its outcome will be the minimum amount of credits held by a member of the group after that round.
Your task is to figure out the maximum possible game outcome, across all possible game endings.

  

 

  
1
  
2
  
3
  
4
 

输入描述:
The first line of the input contains two integers N and S.
Each of the N following lines contains a single integer, the (i + 1)-th line containing the amount of credits Ciinitially owned by member i.
输出描述:
The output should contain a single integer value C corresponding to the maximum possible game outcome.
示例1
输入
复制
3 10
24
42
38
输出
复制
28
说明
The game proceeds as follows:
After round 1 the amounts of credits held are 44, 32, 28 and the minimum is 28.
After round 2 the amounts of credits held are 34, 52, 18 and the minimum is 18.
After round 3 the amounts of credits held are 24, 42, 38 and the minimum is 24.
The best possible outcome is therefore 28, which corresponds to ending the game after round 1.

备注:
1\leq N \leq 100,0001≤N≤100000
1\leq S \leq 100,000,0001≤S≤100000000
for all,1\leq C_i \leq 100,000,0001≤C
i
​
≤100000000 and S \times (N-1) \leq C_iS×(N−1)≤C
i
​
.

• 可以发现到第i轮位为止，前i个数都+ni-si，后面的数都减去si
• 维护前缀最小值和后缀最小值，然后枚举n轮，每次O1算出两个区间的最小值，更新答案最大值

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
LL a[maxn], b[maxn], c[maxn];
int main(){
	memset(b,0x3f,sizeof(b));
	memset(c,0x3f,sizeof(c));
	LL n, s;  cin>>n>>s;
	for(LL i = 1; i <= n; i++){
		cin>>a[i];
		b[i] = min(b[i-1],a[i]);
	}
	for(LL i = n; i >= 1; i--){
		c[i] = min(c[i+1],a[i]);
	}
	LL ans = 0;
	for(LL i = 1; i <= n; i++){
		LL t = min(b[i]+n*s-i*s,c[i+1]-i*s);
		ans = max(ans,t);
	}
	cout<<ans<<"\n";
	return 0;
}


  

 

  
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
 

C. Statues DP

链接：https://ac.nowcoder.com/acm/contest/13977/C
来源：牛客网

To escape the loneliness of working remotely everyday, Erika decided to try on a new hobby:
sculpture. She already has a large collection of statues and the municipality has allowed her to show
her art outside.
Erika wants her statues to be well visible and thus each statue needs to be placed under a distinct
street light. Further, the arrangement should be aesthetic which means that the statues should be
placed by increasing size with the smallest statues near the beginning of the street and the biggest ones
near the end.
Erika placed her statues but she forgot to place them in increasing size and now she has to reposition
them in accordance to both of her desires.
The street has N evenly spaced street lights numbered from 1 at the beginning of the street to N at
the end of the street. You estimate the time required to move a statue of size s from the street light i
to the light j as taking Erika s × |i − j| units of time. You ask yourself, how much time does it take
to reposition all statues knowing that she will use the fastest way possible? Note that she may put
statues under street lights that do not have statues at the moment.

输入描述:
The first line of the input contains two space-separated integers: N the number of street lights and K
the number of statues. The K following lines each contains two space-separated integers, the i + 1-th
line containing the integers Pi and Si describing the i-th statue. Pi gives the number of the street light
under which the statue is and Si gives its size.
输出描述:
The output should contain a single line containing a single integer: the minimum amount of time
needed to move statues such that each statue is under a different street light and such that the size of
statues grows with the street light numbers under which they are.
示例1
输入
复制
3 3
1 3
2 2
3 1
输出
复制
8
说明
Because there are as many street lights as there are statues we needto position the statue of size 1 at street light 1 (which takes 1\times |3-1=2|1×∣3−1=2∣units of times), leave the statue of size 2 atstreet light 2, and move the statue of size 3 to the street light 3(which takes 3
\times |1-3|=63×∣1−3∣=6units of times). In total this takes 88units of time.
示例2
输入
复制
4 3
2 2
3 2
4 1
输出
复制
3
说明
The fastest way of fixing the ordering of statues is to move
the statue of size 1 to the street light 1 for a total time of 1\times
|4-1|=31×∣4−1∣=3.
备注:
1 \leq K \leq N \leq 5,0001≤K≤N≤5000
for all 1 \leq i\leq K1≤i≤K,1\leq S_{i}\leq 1,000,0001≤S
i
​
≤1000000,1\leq P_i \leq N1≤P
i
​
≤N

• 先把雕像排序，从终态出发
• dp到第i个灯为止，放了j个雕像所花费的最小代价
• （最开始dp了到第i个灯为止的最小代价，每次交换了数，没有考虑第二维，不具有最优子结构）

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 5e3+10;
const LL inf = 1e18+10;

struct node{int p,w;}a[maxn];
bool cmp(node a, node b){//pair的排序方式,WA
	if(a.w!=b.w)return a.w<b.w;
	return a.p<b.p;
}

LL f[maxn][maxn];//到第i个灯为止，放了j个雕像所花费的最小代价

int main(){
	int n, k;  cin>>n>>k;
	for(int i = 1; i <= k; i++)
		cin>>a[i].p>>a[i].w;
	sort(a+1,a+k+1,cmp);
	memset(f,0x3f,sizeof(f));
	for(int i = 0; i <= n; i++)f[i][0] = 0;
	//for(int i = 0; i <= n; i++)
	//	for(int j = 1; j <= k; j++)
	//		f[i][j] = inf;
	f[0][0] = 0LL;
	for(int i = 1; i <= n; i++){
		for(int j = 0; j<=min(i,k); j++){
			f[i][j] = f[i-1][j];//第i个位置不放灯
			if(j>0)f[i][j]=min(f[i][j],f[i-1][j-1]+1LL*a[j].w*abs(a[j].p-i));//第i个位置放灯
		}
	}
	cout<<f[n][k]<<"\n";
	return 0;
}


  

 

  
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
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/115407688