GDUT 第二场排位赛

G. Snow Boots

题目链接：http://codeforces.com/group/NVaJtLaLjS/contest/238204/problem/G
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output

It’s winter on the farm, and that means snow! There are N tiles on the path from the farmhouse to the barn, conveniently numbered 1…N, and tile i is covered in fi feet of snow.

Farmer John starts off on tile 1 and must reach tile N to wake up the cows. Tile 1 is sheltered by the farmhouse roof, and tile N is sheltered by the barn roof, so neither of these tiles has any snow. But to step on the other tiles, Farmer John needs to wear boots!

In his foul-weather backpack, Farmer John has B pairs of boots, numbered 1…B. Some pairs are more heavy-duty than others, and some pairs are more agile than others. In particular, pair i lets FJ step in snow at most si feet deep, and lets FJ move at most di forward in each step.

Unfortunately, the boots are packed in such a way that Farmer John can only access the topmost pair at any given time. So at any time, Farmer John can either put on the topmost pair of boots (discarding his old pair) or discard the topmost pair of boots (making a new pair of boots accessible).

Farmer John can only change boots while standing on a tile. If that tile has f feet of snow, both the boots he takes off AND the boots he puts on must be able to withstand at least f feet of snow. Intermediate pairs of boots which he discards without wearing do not need to satisfy this restriction.

Help Farmer John minimize waste, by determining the minimum number of pairs of boots he needs to discard in order to reach the barn. You may assume that Farmer John is initially not wearing any boots.

Input

The first line contains two space-separated integers N and B (2≤N,B≤250).

The second line contains N space-separated integers. The ith integer is fi, giving the depth of snow on tile i (0≤fi≤109). It’s guaranteed that f1=fN=0.

The next B lines contain two space-separated integers each. The first integer on line i+2 is si, the maximum depth of snow in which pair i can step. The second integer on line i+2 is di, the maximum step size for pair i. It’s guaranteed that 0≤si≤109 and 1≤di≤N−1.

The boots are described in top-to-bottom order, so pair 1 is the topmost pair in FJ’s backpack, and so forth.

Output

The output should consist of a single integer, giving the minimum number of boots Farmer John needs to discard. It’s guaranteed that it will be possible for FJ to make it to the barn.

Example

input

10 4
0 2 8 3 6 7 5 1 4 0
2 3
4 2
3 4
7 1

output

2

题目大意：

有n双鞋子，在任何时候穿上最上面的一双靴子或丢弃最上面的一双靴子，如果瓷砖上有F英尺的雪，那么他脱下的靴子和穿上的靴子都必须至少能承受F英尺的雪。他不穿就丢弃的中靴不需要满足这一限制。农夫约翰一开始没有穿靴子。确定到达谷仓所需丢弃的靴子的最少数量。

题目思路：

这题很明显就是dp啦，穿与不穿，求最优解。建个二维数组，第一个是走到第几格，第二个是用了几个鞋子了。每次就考虑换不换鞋子。

代码：

#include <bits/stdc++.h>
#define maxn 255
using namespace std;

int f[maxn],d[maxn],s[maxn];
int dp[maxn][maxn]; //第一个maxn是走到第几格，第二个是用了几个鞋子了
int n,b;

int main(){
   cin>>n>>b;
   for(int i=1;i<=n;i++) cin>>f[i];
   for(int i=1;i<=b;i++){
    cin>>s[i]>>d[i];
   }
   dp[1][1]=1;
   for(int i=1;i<=n;i++){
    for(int j=1;j<=b;j++){
        if(f[i]>s[j]) continue;  //不成立的跳过
        for(int t=1;t<i;t++){    //考虑换鞋子的时候
            if(i-t<=d[j]&&f[t]<=s[j]&&dp[t][j])
                dp[i][j]=1;
        }
        for(int k=1;k<j;k++){    //考虑不换鞋子的时候
            if(f[i]<d[k]&&dp[i][k])
                dp[i][j]=1;
        }
    }
   }
    for(int i=0;i<=n;i++){
        if(dp[n][i]==1){       //最开始是没鞋子的，但从一开始算起了，所以要减去
            cout<<i-1<<endl;
            return 0;
        }
    }
}

E. Taming the Herd

题目链接：http://codeforces.com/group/NVaJtLaLjS/contest/238204/problem/E
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output

Early in the morning, Farmer John woke up to the sound of splintering wood. It was the cows, and they were breaking out of the barn again!

Farmer John was sick and tired of the cows’ morning breakouts, and he decided enough was enough: it was time to get tough. He nailed to the barn wall a counter tracking the number of days since the last breakout. So if a breakout occurred in the morning, the counter would be 0 that day; if the most recent breakout was 3 days ago, the counter would read 3. Farmer John meticulously logged the counter every day.

The end of the year has come, and Farmer John is ready to do some accounting. The cows will pay, he says! But something about his log doesn’t look quite right…

Farmer John wants to find out how many breakouts have occurred since he started his log. However, he suspects that the cows have tampered with his log, and all he knows for sure is that he started his log on the day of a breakout. Please help him determine, for each number of breakouts that might have occurred since he started the log, the minimum number of log entries that must have been tampered with.

Input

The first line contains a single integer N (1≤N≤100), denoting the number of days since Farmer John started logging the cow breakout counter.

The second line contains N space-separated integers. The ith integer is a non-negative integer ai (at most 100), indicating that on day i the counter was at ai, unless the cows tampered with that day’s log entry.

Output

The output should consist of N integers, one per line. The ith integer should be the minimum over all possible breakout sequences with i breakouts, of the number of log entries that are inconsistent with that sequence.

Example

input

6
1 1 2 0 0 1

output

4
2
1
2
3
4

Note

If there was only 1 breakout, then the correct log would look like 0 1 2 3 4 5, which is 4 entries different from the given log.

If there were 2 breakouts, then the correct log might look like 0 1 2 3 0 1, which is 2 entries different from the given log. In this case, the breakouts occurred on the first and fifth days.

If there were 3 breakouts, then the correct log might look like 0 1 2 0 0 1, which is just 1 entry different from the given log. In this case, the breakouts occurred on the first, fourth, and fifth days.

And so on.

题目大意：

有一个计数器，记录上次突破后的天数。他怀疑奶牛篡改了他的日志，他所知道的就是他在突破的那天开始记录。请帮助他确定，对于他启动日志后可能发生的每个断开数，必须被篡改的最小日志条目数。输出第i个整数应该是具有i个中断的所有可能中断序列中与该序列不一致的日志条目数的最小值。

题目思路：

题目很难看出是动态规划（当时我也没想出来QAQ），建立一个三维数组，第一个是几天，第二个是第几个中断，第三个是不一致的可能值，然后建立状态方程即可：

if(!k) dp[i][j][k]=g[i-1][j-1]+(a[i]!=0); 
     else dp[i][j][k]=dp[i-1][j][k-1]+(a[i]!=k);
     g[i][j]=min(g[i][j],dp[i][j][k]);

代码：

#include <bits/stdc++.h>
using namespace std;
const int M=110,inf=0x3f3f3f3f;
int n,a[M],dp[M][M][M],g[M][M];//dp的第一个M是第几天，第二个M是第几个中断，第三个是不一致的可能值
int main(){
  memset(dp,inf,sizeof(dp));
  memset(g,inf,sizeof(g));
  cin>>n;
  for(int i=1;i<=n;i++) cin>>a[i];
  dp[0][0][0]=g[0][0]=0;
  for(int i=1;i<=n;i++)
  for(int j=1;j<=i;j++)
  for(int k=0;k<i;k++){
     if(!k) dp[i][j][k]=g[i-1][j-1]+(a[i]!=0); 
     else dp[i][j][k]=dp[i-1][j][k-1]+(a[i]!=k);
     g[i][j]=min(g[i][j],dp[i][j][k]);
    }
      for(int i=1;i<=n;i++)
        cout<<g[n][i]<<endl;
      return 0;
}

A. Taming the Herd

time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output

Early in the morning, Farmer John woke up to the sound of splintering wood. It was the cows, and they were breaking out of the barn again!

Farmer John was sick and tired of the cows’ morning breakouts, and he decided enough was enough: it was time to get tough. He nailed to the barn wall a counter tracking the number of days since the last breakout. So if a breakout occurred in the morning, the counter would be 0 that day; if the most recent breakout was 3 days ago, the counter would read 3. Farmer John meticulously logged the counter every day.

The end of the year has come, and Farmer John is ready to do some accounting. The cows will pay, he says! But lo and behold, some entries of his log are missing!

Farmer John is confident that the he started his log on the day of a breakout. Please help him determine, out of all sequences of events consistent with the log entries that remain, the minimum and maximum number of breakouts that may have take place over the course of the logged time.

Input

The first line contains a single integer N (1≤N≤100), denoting the number of days since Farmer John started logging the cow breakout counter.

The second line contains N space-separated integers. The ith integer is either −1, indicating that the log entry for day i is missing, or a non-negative integer ai (at most 100), indicating that on day i the counter was at ai.

Output

If there is no sequence of events consistent with Farmer John’s partial log and his knowledge that the cows definitely broke out of the barn on the morning of day 1, output a single integer −1. Otherwise, output two space-separated integers m followed by M, where m is the minimum number of breakouts of any consistent sequence of events, and M is the maximum.

Example

input

4
-1 -1 -1 1

output

2 3

Note

In this example, we can deduce that a breakout had to occur on day 3. Knowing that a breakout also occurred on day 1, the only remaining bit of uncertainty is whether a breakout occurred on day 2. Hence, there were between 2 and 3 breakouts in total.

题目大意：

有个计数器，记录上次突破后的天数。且在突破日开始记录的。不一致就输出-1。否则输出最大突破数，输出最小突破数。

题目思路：

直接暴力加修改，如果不符合，加个标记，如果未知就修改成正确的，最后的答案就是已知的加起来就是最小的，再加上修改后还是未知的点。

注意：第一天一定是突破日，记得排除。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long

int main(){
  int n,flag=0,ans=0,r;
  int a[105];
  memset(a,0,sizeof(a));
  cin>>n;
  for(int i=0;i<n;i++){
  cin>>a[i];
  }
  
   if(n==1&&a[0]!=-1&&a[0]!=0){
           flag=1;
   }
   
  for(int i=1;i<n;i++){
        if(a[i]!=-1){
    if(i-a[i]<0) flag=1;}
    if(a[0]!=0){
        if(a[0]!=-1){
            flag=1;
        }
    }
  }
  
  for(int i=1;i<n;i++){
    if(a[i]!=-1&&a[i]!=0){
        for(int j=1;j<=a[i];j++){
           if(a[i-j]==-1){
            a[i-j]=a[i]-j;
           }
           if(a[i-j]!=-1){
            if(a[i-j]!=a[i]-j)
                flag=1;
           }
        }
    }
  }
        for(int i=1;i<n;i++){
            if(a[i]==0)
                ans++;
        }
  r=ans;
  for(int i=1;i<n;i++){
    if(a[i]==-1) ans++;
  }
  if(flag==1) cout<<-1<<endl;
  else cout<<r+1<<" "<<ans+1<<endl;
}

C. Rest Stops

time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output

Farmer John and his personal trainer Bessie are hiking up Mount Vancowver. For their purposes (and yours), the mountain can be represented as a long straight trail of length L meters (1≤L≤106). Farmer John will hike the trail at a constant travel rate of rF seconds per meter (1≤rF≤106). Since he is working on his stamina, he will not take any rest stops along the way.

Bessie, however, is allowed to take rest stops, where she might find some tasty grass. Of course, she cannot stop just anywhere! There are N rest stops along the trail (1≤N≤105); the i-th stop is xi meters from the start of the trail (0<xi<L) and has a tastiness value ci (1≤ci≤106). If Bessie rests at stop i for t seconds, she receives ci⋅t tastiness units.

When not at a rest stop, Bessie will be hiking at a fixed travel rate of rB seconds per meter (1≤rB≤106). Since Bessie is young and fit, rB is strictly less than rF.

Bessie would like to maximize her consumption of tasty grass. But she is worried about Farmer John; she thinks that if at any point along the hike she is behind Farmer John on the trail, he might lose all motivation to continue!

Help Bessie find the maximum total tastiness units she can obtain while making sure that Farmer John completes the hike.

Input

The first line of input contains four integers: L, N, rF, and rB. The next N lines describe the rest stops. For each i between 1 and N, the i+1-st line contains two integers xi and ci, describing the position of the i-th rest stop and the tastiness of the grass there.

It is guaranteed that rF>rB, and 0<x1<…<xN<L. Note that rF and rB are given in seconds per meter!

Output

A single integer: the maximum total tastiness units Bessie can obtain.

Example

input

10 2 4 3
7 2
8 1

output

15

Note

In this example, it is optimal for Bessie to stop for 7 seconds at the x=7 rest stop (acquiring 14 tastiness units) and then stop for an additional 1 second at the x=8 rest stop (acquiring 1 more tastiness unit, for a total of 15 tastiness units).

题目大意：

在一个跑道上有很多个站可以补充能量，一个奶牛在后面追另一个奶牛，前面的奶牛不能被追上，然后可以选择站补充能量，请问要怎样才能获得最大的能量。

题目思路：

找出跑道上能量最大的站，然后继续剩下的取最大，直到终点，如此贪心即是答案。
注意：上面的速度是走一米用几秒。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long

struct node{
  int x,v;
}a[1000005];

bool cmp(const node&c,const node&b){
  if(c.v==b.v) return c.x>b.x;
    else return c.v>b.v;
}

int main(){

    ll L,N,rf,rb,num=0;
  cin>>L>>N>>rf>>rb;
  for(int i=0;i<N;i++){
    cin>>a[i].x>>a[i].v;
  }
  sort(a,a+N,cmp);
   ll maxs=a[0].x;
  num=a[0].v*maxs*(rf-rb);

  for(int i=1;i<N;i++){
      if(a[i].x<maxs)
        continue;
        num+=a[i].v*(a[i].x-maxs)*(rf-rb);
        maxs=a[i].x;
  }
  cout<<num<<endl;
  return 0;
}

B. Hoofball

time limit per test5 seconds
memory limit per test512 megabytes
inputstandard input
outputstandard output

In preparation for the upcoming hoofball tournament, Farmer John is drilling his N cows (conveniently numbered 1…N, where 1≤N≤100) in passing the ball. The cows are all standing along a very long line on one side of the barn, with cow i standing xi units away from the barn (1≤xi≤1000). Each cow is standing at a distinct location.

At the beginning of the drill, Farmer John will pass several balls to different cows. When cow i receives a ball, either from Farmer John or from another cow, she will pass the ball to the cow nearest her (and if multiple cows are the same distance from her, she will pass the ball to the cow farthest to the left among these). So that all cows get at least a little bit of practice passing, Farmer John wants to make sure that every cow will hold a ball at least once. Help him figure out the minimum number of balls he needs to distribute initially to ensure this can happen, assuming he hands the balls to an appropriate initial set of cows.

Input

The first line of input contains N. The second line contains N space-separated integers, where the ith integer is xi.

Output

Please output the minimum number of balls Farmer John must initially pass to the cows, so that every cow can hold a ball at least once.

Example

inputCopy

5
7 1 3 11 4

outputCopy

2

Note

In the above example, Farmer John should pass a ball to the cow at x=1 and pass a ball to the cow at x=11. The cow at x=1 will pass her ball to the cow at x=3, after which this ball will oscillate between the cow at x=3 and the cow at x=4. The cow at x=11 will pass her ball to the cow at x=7, who will pass the ball to the cow at x=4, after which this ball will also cycle between the cow at x=3 and the cow at x=4. In this way, all cows will be passed a ball at least once (possibly by Farmer John, possibly by another cow).

It can be seen that there is no single cow to whom Farmer John could initially pass a ball

so that every cow would eventually be passed a ball.

这道题有各种花里胡哨的解法。
先介绍一种模拟的方法：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long

int main(){
  ll n,a[110],flag[110],vis[110],next[110];
  memset(flag,0,sizeof(flag));
  memset(vis,0,sizeof(vis));
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>a[i];
  }
  if(n==1||n==2){
    cout<<1<<endl;
    return 0;
  }
  sort(a+1,a+n+1);
  for(int i=1;i<=n;i++){  //记录每个点要到的下一个点
    if(i==1) next[i]=2;
    else if(i==n){
        next[i]=n-1;}
        else{
            if(a[i]-a[i-1]<=a[i+1]-a[i])
                next[i]=i-1;
            else
                next[i]=i+1;
        }

    }
    for(int i=1;i<=n;i++)
        if(next[next[i]]==i)  //判断是否成环
        flag[i]=1;
    ll ans=0;
    for(int i=1;i<=n;i++){ 
        if(flag[i]&&flag[i+1]&&!vis[i]&&!vis[i+1]){
            if(i>1&&i<n&&next[i-1]==i&&next[i+2]==i+1)
                ans+=2;
            else
                ans+=1;
            vis[i]=vis[i+1]=1;
        }

    }
    cout<<ans<<endl;
    return 0;
}

看别人的比赛代码，发现还有一种用DFS模拟的做法(能想出来的都是大佬）

#include<cstdio>
#include<cstdlib>
#include<string> 
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
int a[105];//位置 
int dis[105][5];//1是左，2是右 
int vis[105];//标记 
int ans[105];
int cnt=1; 
int dfs(int i)
{
	if(vis[i]==cnt)
		return 0;
	vis[i]=cnt;
	if(dis[i][1]==0) //如果是端点，走对的那条 
		dfs(i+1);
	else if(dis[i][2]==0)
		dfs(i-1);
	else if(dis[i][1]!=0&&dis[i][2]!=0)//如果不是端点,继续搜 
	{
		if(dis[i][1]<dis[i][2])
			dfs(i-1);
		else if(dis[i][1]>dis[i][2])
			dfs(i+1);
		else//两边一样近 ,给左边 
			dfs(i-1);
	}
	return 0;
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+n+1);//从左到右排
	dis[1][2]=a[2]-a[1];
	dis[n][1]=a[n]-a[n-1];
	for(int i=2;i<n;i++){
		dis[i][1]=a[i]-a[i-1];
		dis[i][2]=a[i+1]-a[i];
	}
	/*
	for(int i=1;i<=n;i++)
			printf("%d 	",a[i]);
	printf("\n");
	for(int i=1;i<=n;i++)
		for(int j=1;j<=2;j++)
			printf("dis[%d][%d]:%d\n",i,j,dis[i][j]); 
			*/
	for(int i=1;i<=n;i++)
	{
		if(vis[i]==0)
			dfs(i);
		cnt++; 
	}	
	for(int i=1;i<=n;i++)
		ans[vis[i]]=1;
	cnt=0;
	for(int i=1;i<=105;i++)
		if(ans[i]==1)
			cnt++;
	printf("%d\n",cnt);
	return 0;
}

还有一种是DP的做法，能写出来的都是巨佬！Orz

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int cow[105];
bool vis[105];
bool fx[105];
int dp[105];
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &cow[i]);
    }
    sort(cow+1, cow+n+1);
    fx[1] = true, fx[n] = false;
    for(int i = 2; i <= n-1; i++)
    {
        if(cow[i]-cow[i-1] <= cow[i+1]-cow[i])
        {
            fx[i] = false;
        }
        else
        {
            fx[i] = true;
        }
    }
    memset(dp, inf, sizeof(dp));
    dp[0] = 0;
    for(int i = 1; i <= n; i++)
    {
        memset(vis, false, sizeof(vis));
        vis[i] = true;
        int maxx = i;
        int minx = i;
        int nxt = fx[i] ? i+1 : i-1;
        while(!vis[nxt])
        {
            vis[nxt] = true;
            maxx = max(maxx , nxt);
            minx = min(minx , nxt);
            nxt = fx[nxt] ? nxt+1 : nxt-1;
        }
        if(minx != i)
        {
            for(int j = minx; j <= i; j++)
            {
                dp[j] = min(dp[j] , dp[minx-1]+1);
            }
        }
        else
        {
            for(int j = i; j<= maxx; j++)
            {
                dp[j] = min(dp[j] , dp[i-1]+1);
            }
        }
    }
    printf("%d\n", dp[n]);
    return 0;
}