I found a problem like this on a website:
Flappy bird is a popular leisure mobile game. Players need to constantly control the frequency of clicking on the mobile phone screen to adjust the bird’s flying height, so that the bird can smoothly pass through the gap on the right side of the screen. If the bird accidentally hits the water pipe or falls to the ground, it will be declared a failure.
In order to simplify the problem, we simplified and adapted the rules of the game
The game interface is a two-dimensional plane with the length of N and the height of m, in which there are K pipes (ignoring the width of the pipe).
Birds always move in the game interface. The bird starts from any integer height position on the left side of the game interface, and when it reaches the right side of the game interface, the game is completed.
The distance of the bird moving right along the abscissa per unit time is 1, and the distance of vertical movement is controlled by the player. If you click on the screen, the bird will rise to a certain height X. You can click multiple times per unit time, and the effect will be superimposed; If you don’t click on the screen, the bird will drop a certain height Y. When the bird is located at different positions in the abscissa direction, the ascending height X and descending height Y may be different from each other.
When the height of the bird is equal to 0 or the bird touches the pipe, the game fails. When the bird height is m\m, it can’t rise again.
Now, please judge whether you can finish the game. If possible, output the minimum number of clicks on the screen; Otherwise, how many pipe gaps can the output bird pass through at most.
Input
In line 11, there are 3 integers n, m, K, which respectively represent the length, height and number of water pipes of the game interface, with a space between each two integers;
In the next N line, there are 2 integers X and Y separated by a space in each line, which successively represent the height X of the bird rising in the next position after the player clicks the screen at the abscissa position 0 ∼ n − 1, and the height Y of the bird falling in the next position when the player does not click the screen at this position.
Next, the K line contains 3 integers P, l, h, separated by a space. Each line represents a pipe, where P represents the abscissa of the pipe, l represents the height of the lower edge of the pipe gap, and H represents the height of the upper edge of the pipe gap (input data to ensure that P is different, but not in the order of size).
Sample
10 10 6
3 9
9 9
1 2
1 3
1 2
1 1
2 1
2 1
1 6
2 2
1 2 7
5 1 5
6 3 5
7 5 8
8 7 9
9 1 3
In this case, output 1 6
I tried this problem, but kept getting a wrong answer. Can you help me with it?
Here is my code:
#include<bits/stdc++.h>
using namespace std;
struct node{
int p,l,h;
};
bool comp(node a,node b){
return a.p<b.p;
}
int n,m,k,x[10005],y[10005],a1,b1,c1,d1,ans=9999999,ans2=0;
int screen=0,dp[10005][1005]={0};
node z[10005];
int fun(int a,int b){
if(b<=0) return 9999999;
if(dp[a][b]) return dp[a][b];
for(int i=0;i<k;i++){
if(a==z[i].p){
if(!(b>z[i].l&&b<z[i].h)){
ans2=max(ans2,i);
return dp[a][b]=9999999;
}
break;
}
}
if(a==n) {
return screen;
}
for(int i=0;b+(i-1)*x[a]<=m;i++){
if(i==0) ans=min(ans,fun(a+1,b-y[a]));
else{
screen+=i;
ans=min(ans,fun(a+1,min(m,b+i*x[a])));
screen-=i;
}
}
return dp[a][b]=ans;
}
int main(){
cin>>n>>m>>k;
for(int i=0;i<n;i++) scanf("%d%d",&x[i],&y[i]);
for(int i=0;i<k;i++) scanf("%d%d%d",&z[i].p,&z[i].l,&z[i].h);
sort(z,z+k,comp);
for(int i=1;i<=m;i++){
int t=fun(0,i);
}
if(ans!=9999999) cout<<1<<endl<<ans;
else cout<<0<<endl<<ans2;
return 0;
}