[已解决]dp求助

aaron0919

我的code

1. 
   
2. #include<bits/stdc++.h>
   
3. using namespace std;
   
4. int a[100000],dp[100000];
   
5. int main(){                             
   
6.     int p,q,n;
   
7.     cin>>p>>q>>n;
   
8.     for(int i=1;i<=n;i++){
   
9.             cin>>a[i];
   
10.         }
    
11.         dp[0]=p;
    
12.         dp[1]=p-q>=0?p-q+a[1]:-1e9;
    
13.         for(int i=2;i<=n+1;i++){
    
14.                 int flag=0;
    
15.                 if(dp[i-1]-q>=0){
    
16.                         dp[i]=max(dp[i],dp[i-1]-q+a[i]);
    
17.                         flag++;
    
18.                 }
    
19.                 if(dp[i-2]-q>=0){
    
20.                         dp[i]=max(dp[i],dp[i-2]-q+a[i]);
    
21.                         flag++;
    
22.                 }
    
23.                 if(!flag){
    
24.                         dp[i]=-1e9;
    
25.                 }
    
26.         }
    
27.         if(dp[n+1]<=0){
    
28.                 cout<<"NO";
    
29.         }else{
    
30.                 cout<<dp[n+1];
    
31.         }
    
32.         return 0;      
    
33. }

复制代码

只能八十分。。。

最佳答案

月排行榜 / 总排行榜

jhq999

2022-11-28 17:00:55

1. #include <stdio.h>
   
2. //int node[1000000];
   
3. 
   
4. 
   
5. int main()
   
6. {
   
7.     int i,P,Q,n,t,prv[3]= {0},cur=0; //cur是跳到当前位置消耗的最小量，
   
8.                                                     //prv[1]prv[2]是当前位置前两个位置消已经耗的能量
   
9.     scanf("%d%d",&P,&Q);
   
10.     scanf("%d",&n);
    
11.     prv[1]=0;
    
12.     scanf("%d",&prv[2]);
    
13.     prv[2]-=Q;
    
14.     for (i=2; i<=n; i+=1)
    
15.     {
    
16.         /*if((P+prv[1]<Q)&&((P+prv[2]<Q))
    
17.         {
    
18.                 printf("NO");
    
19.                 return 0;
    
20.         }*/
    
21.         
    
22.         if(prv[1]>prv[2])t=prv[1];//选前两个位置消耗最少的
    
23.         else t=prv[2];
    
24.         if(P+t<Q)
    
25.         {
    
26.                 printf("NO");
    
27.                 return 0;
    
28.         }
    
29.         scanf("%d",&cur);//当前位置的能量ai
    
30.         cur+=t-Q;//当前位置的能量ai减去跳一次消耗的能量再加上前两个能量消耗最少的
    
31.         prv[1]=prv[2];
    
32.         prv[2]=cur;
    
33. 
    
34.     }
    
35.     if(prv[1]>prv[2])t=prv[1];
    
36.     else t=prv[2];//终点前两个位置消耗最少的
    
37.     if(P+t<Q)
    
38.     {
    
39.                 printf("NO");
    
40.                 return 0;
    
41.      }
    
42.     printf("%d",P+t-Q);
    
43.     return 0;
    
44. }
    

复制代码

跳转到最佳答案楼层

jhq999

1. #include <stdio.h>
   
2. //int node[1000000];
   
3. 
   
4. 
   
5. int main()
   
6. {
   
7.     int i,P,Q,n,t,prv[3]= {0},cur=0; //cur是跳到当前位置消耗的最小量，
   
8.                                                     //prv[1]prv[2]是当前位置前两个位置消已经耗的能量
   
9.     scanf("%d%d",&P,&Q);
   
10.     scanf("%d",&n);
    
11.     prv[1]=0;
    
12.     scanf("%d",&prv[2]);
    
13.     prv[2]-=Q;
    
14.     for (i=2; i<=n; i+=1)
    
15.     {
    
16.         /*if((P+prv[1]<Q)&&((P+prv[2]<Q))
    
17.         {
    
18.                 printf("NO");
    
19.                 return 0;
    
20.         }*/
    
21.         
    
22.         if(prv[1]>prv[2])t=prv[1];//选前两个位置消耗最少的
    
23.         else t=prv[2];
    
24.         if(P+t<Q)
    
25.         {
    
26.                 printf("NO");
    
27.                 return 0;
    
28.         }
    
29.         scanf("%d",&cur);//当前位置的能量ai
    
30.         cur+=t-Q;//当前位置的能量ai减去跳一次消耗的能量再加上前两个能量消耗最少的
    
31.         prv[1]=prv[2];
    
32.         prv[2]=cur;
    
33. 
    
34.     }
    
35.     if(prv[1]>prv[2])t=prv[1];
    
36.     else t=prv[2];//终点前两个位置消耗最少的
    
37.     if(P+t<Q)
    
38.     {
    
39.                 printf("NO");
    
40.                 return 0;
    
41.      }
    
42.     printf("%d",P+t-Q);
    
43.     return 0;
    
44. }
    

复制代码