[已解决]dp求助

aaron0919

我的code

#include<bits/stdc++.h>
using namespace std;
int a[100000],dp[100000];
int main(){                             
    int p,q,n;
    cin>>p>>q>>n;
    for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        dp[0]=p;
        dp[1]=p-q>=0?p-q+a[1]:-1e9;
        for(int i=2;i<=n+1;i++){
                int flag=0;
                if(dp[i-1]-q>=0){
                        dp[i]=max(dp[i],dp[i-1]-q+a[i]);
                        flag++;
                }
                if(dp[i-2]-q>=0){
                        dp[i]=max(dp[i],dp[i-2]-q+a[i]);
                        flag++;
                }
                if(!flag){
                        dp[i]=-1e9;
                }
        }
        if(dp[n+1]<=0){
                cout<<"NO";
        }else{
                cout<<dp[n+1];
        }
        return 0;      
}

只能八十分。。。

最佳答案

月排行榜 / 总排行榜

jhq999

2022-11-28 17:00:55

#include <stdio.h>
//int node[1000000];


int main()
{
    int i,P,Q,n,t,prv[3]= {0},cur=0; //cur是跳到当前位置消耗的最小量，
                                                    //prv[1]prv[2]是当前位置前两个位置消已经耗的能量
    scanf("%d%d",&P,&Q);
    scanf("%d",&n);
    prv[1]=0;
    scanf("%d",&prv[2]);
    prv[2]-=Q;
    for (i=2; i<=n; i+=1)
    {
        /*if((P+prv[1]<Q)&&((P+prv[2]<Q))
        {
                printf("NO");
                return 0;
        }*/
        
        if(prv[1]>prv[2])t=prv[1];//选前两个位置消耗最少的
        else t=prv[2];
        if(P+t<Q)
        {
                printf("NO");
                return 0;
        }
        scanf("%d",&cur);//当前位置的能量ai
        cur+=t-Q;//当前位置的能量ai减去跳一次消耗的能量再加上前两个能量消耗最少的
        prv[1]=prv[2];
        prv[2]=cur;

    }
    if(prv[1]>prv[2])t=prv[1];
    else t=prv[2];//终点前两个位置消耗最少的
    if(P+t<Q)
    {
                printf("NO");
                return 0;
     }
    printf("%d",P+t-Q);
    return 0;
}

跳转到最佳答案楼层

jhq999

#include <stdio.h>
//int node[1000000];


int main()
{
    int i,P,Q,n,t,prv[3]= {0},cur=0; //cur是跳到当前位置消耗的最小量，
                                                    //prv[1]prv[2]是当前位置前两个位置消已经耗的能量
    scanf("%d%d",&P,&Q);
    scanf("%d",&n);
    prv[1]=0;
    scanf("%d",&prv[2]);
    prv[2]-=Q;
    for (i=2; i<=n; i+=1)
    {
        /*if((P+prv[1]<Q)&&((P+prv[2]<Q))
        {
                printf("NO");
                return 0;
        }*/
        
        if(prv[1]>prv[2])t=prv[1];//选前两个位置消耗最少的
        else t=prv[2];
        if(P+t<Q)
        {
                printf("NO");
                return 0;
        }
        scanf("%d",&cur);//当前位置的能量ai
        cur+=t-Q;//当前位置的能量ai减去跳一次消耗的能量再加上前两个能量消耗最少的
        prv[1]=prv[2];
        prv[2]=cur;

    }
    if(prv[1]>prv[2])t=prv[1];
    else t=prv[2];//终点前两个位置消耗最少的
    if(P+t<Q)
    {
                printf("NO");
                return 0;
     }
    printf("%d",P+t-Q);
    return 0;
}