赛后补题：暑期集训

BAPC 2014 Preliminary

D. Lift Problems

https://nanti.jisuanke.com/t/28204

题意：给一串数字代表每个楼层的人数，如果电梯停在某一层，那么愤怒值增加相当于后面没到的人数；如果电梯过了某一层没停，那么愤怒值增加这层楼层到下一次停靠楼层差与这层要下电梯人数的乘机。

思路：动态规划。

用A[i]表示到达楼层i的最小愤怒值，则有:

其中，第二项表示的是停靠在某一层过站人的愤怒，第三项表示没到人的愤怒。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main(){
 5     int t,n,dp[1510],a[1510];
 6     scanf("%d",&t);
 7     while(t--){
 8         memset(dp,0x3f,sizeof(dp));
 9         memset(a,0,sizeof(a));
10         int sum=0;
11         scanf("%d",&n);
12         for(int i=1;i<=n;i++){
13             scanf("%d",&a[i]);
14             sum+=a[i];
15         }
16         dp[0]=0;
17         for(int i=1;i<=n;i++){
18             sum-=a[i];
19             int k=0;
20             for(int j=i-1;j>=0;j--){
21                 dp[i]=min(dp[i],dp[j]+sum+k);
22                 k=k+(i-j)*a[j];
23             }
24         }
25         printf("%d
",dp[n]);
26 
27     }
28 }

View Code

Benelux Algorithm Programming Contest 2014 Final

B. Button Bashing

题意：n个按钮，每个按钮可以加减一定时长，求0到大于等于给定数字m需要至少多少次按钮，并求出最少超出时间。

做法：bfs打出3600秒内可达时间及次数。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int tim[20],vis[3610];
 4 int con,n,m;
 5 
 6 int main(){
 7     int t;
 8     scanf("%d",&t);
 9     
10     while(t--){
11         
12         memset(vis,0x3f,sizeof(vis));
13         vis[0]=0;
14         con=0;
15         scanf("%d%d",&n,&m);
16         for(int i=0;i<n;i++){
17             scanf("%d",&tim[i]);
18         }
19         queue<int> q;
20         q.push(0);
21         while(!q.empty()){
22             int now=q.front();
23             q.pop();
24             for(int i=0;i<n;i++){
25                 int next=now+tim[i];
26                 if(next<0)next=0;
27                 if(next>3600)next=3600;
28                 if(vis[next]<=vis[now]+1)continue;
29                 vis[next]=vis[now]+1;
30                 q.push(next);
31             }
32         }
33         int z;
34         for(z=m;z<=3600;z++){
35             if(vis[z]!=0x3f3f3f3f){
36                 break;
37             }
38         }
39         printf("%d %d
",vis[z],z-m);
40     }
41     return 0;
42 }

View Code