[Gym-101550D] 贪心

﹏ヽ暗。殇╰゛Y 2024-04-17 23:44 36阅读 0赞

一道题贪心题，硬生生的让我做成了dp

###### 思路： ######

低价买  
高价卖  
找非递减子序列（就是将该段序列 看成多个 非递减子序列的拼接 ）

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    ll p[400];
    int main()
    { 
        ios_base::sync_with_stdio(false);
        ll d;
        cin>>d;
    
        for(ll i = 1;i <= d;i++)cin>>p[i];
    
        ll money = 100;
        ll pre = 0x3f3f3f3f;//初始化之前的价格为无穷大
        for(ll i = 1;i <= d;i++)
        { 
            if(p[i] >= pre)// 如果当前价格大于之前的价格， 当前价格就要卖
            { 
                ll mi = min(100000ll, money/pre);//最多只能买1e5张所以取最小，money/pre 是上次最大可能的股数（这一步就是反悔的一步）
                money = mi*p[i]+(money - mi*pre);// 计算现在的价钱 
    
            }
            pre = p[i];
        }
        cout <<money;
    
    
    
        return 0;
    }

[更好理解的代码,思路一样][Link 1]

硬生生的dp思路：  
每个一天有两种状态：  
状态①：股票最多  
状态②：钱最多。

#### dp代码（有点乱） ####

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    struct node
    { 
        ll m;
        ll num;
    } dp[400][2]; // 0 pio 1 qian
    ll a[400];
    int main()
    { 
        ios_base::sync_with_stdio(false);
        ll n;
        cin>>n;
    
        for(ll i = 1; i <= n; i++)
        { 
            cin>>a[i];
        }
        dp[0][0].m = 100;
        dp[0][0].num = 0;
        dp[0][1].m = 100;
        dp[0][1].num = 0;
        ll mx = 100;
        for(int i = 1; i <= n; i++)
        { 
            if(dp[i-1][0].num == 100000)
            { 
                dp[i][0].num = 100000;
                dp[i][0].m = dp[i-1][0].m;
                if(dp[i-1][1].num+dp[i-1][1].m/a[i]>= 100000)
                { 
                    dp[i][0].m =max(dp[i-1][0].m, dp[i-1][1].m-(a[i]*(100000-dp[i-1][1].num)));
                }
    
            }
            else
            { 
                if(dp[i-1][1].m/a[i]+dp[i-1][1].num >= 100000&&dp[i-1][0].num+dp[i-1][0].m/a[i]>= 100000)
                { 
                    dp[i][0].num = 100000;
                    dp[i][0].m = max(dp[i-1][1].m-(100000-dp[i-1][1].num)*a[i],dp[i-1][0].m-(100000-dp[i-1][0].num)*a[i]);
                }
                else  if(dp[i-1][1].m/a[i]+dp[i-1][1].num >= 100000)
                { 
                     dp[i][0].num = 100000;
                    dp[i][0].m = dp[i-1][1].m-(100000-dp[i-1][1].num)*a[i];
                }
                else if(dp[i-1][0].num+dp[i-1][0].m/a[i]>= 100000)
                { 
                     dp[i][0].num = 100000;
                    dp[i][0].m = dp[i-1][0].m-(100000-dp[i-1][0].num)*a[i];
                }
                else
                if(dp[i-1][1].m/a[i]+dp[i-1][1].num > dp[i-1][0].num+dp[i-1][0].m/a[i])
                { 
                    dp[i][0].num = dp[i-1][1].m/a[i]+dp[i-1][1].num;
                    dp[i][0].m = dp[i-1][1].m%a[i];
                }
                else if(dp[i-1][1].m/a[i]+dp[i-1][1].num== dp[i-1][0].num+dp[i-1][0].m/a[i])
                { 
                    dp[i][0].num = dp[i-1][1].m/a[i]+dp[i-1][1].num;
                    dp[i][0].m = max(dp[i-1][1].m%a[i],dp[i-1][0].m%a[i]);
                }
                else if(dp[i-1][1].m/a[i]+dp[i-1][1].num < dp[i-1][0].num+dp[i-1][0].m/a[i])
                { 
                    dp[i][0].num = dp[i-1][0].num+dp[i-1][0].m/a[i];
                    dp[i][0].m = dp[i-1][0].m%a[i];
                }
            }
    
    
            dp[i][1].m = max(dp[i-1][0].m+dp[i-1][0].num*a[i],dp[i-1][1].m+dp[i-1][1].num*a[i]);
            dp[i][1].num = 0;
            mx = max(mx, max(dp[i][0].m, dp[i][1].m));
    
        }
        cout <<mx<<endl;
    
    
    
    
    
    }

[Link 1]: https://blog.csdn.net/hao_zong_yin/article/details/82964186