思路: 之前做过一遍这个题目,现在又看了一遍,刚开始没看懂题目,后来才发现要求在每连续 5 5 5月都亏损的情况下输出最大利润,若某个月盈利则获 s s s,否则亏损 d d d元. 考虑每个月选择盈利还是亏损,根据贪心的思想,我们肯定是优先选择前面的月作为 s s s,这样后面就能用较少的 d d d就能在给较多的表单作贡献,从而放更多的 s s s.
分类讨论:
1.每个月只有一个 d ( d > 4 s ) d\ (d>4s) d (d>4s) s s s s d s s s s d s s , a n s = 10 s − 2 d ssssd\ ssssd\ ss,ans=10s-2d ssssd ssssd ss,ans=10s−2d 2.每个月两个 d ( 2 d > 3 s ) d\ (2d>3s) d (2d>3s) s s s d d s s s d d s s , a n s = 8 s − 4 d sssdd\ sssdd\ ss,ans=8s-4d sssdd sssdd ss,ans=8s−4d 3.每个月 3 3 3个 d ( 3 d > 2 s ) d\ (3d>2s) d (3d>2s) s s d d d s s d d d s s , a n s = 6 s − 6 d ssddd\ ssddd\ ss,ans=6s-6d ssddd ssddd ss,ans=6s−6d 4.每个月 4 4 4个 d ( 4 d > s ) d\ (4d>s) d (4d>s) s d d d d s d d d d s d , a n s = 3 s − 9 d sdddd\ sdddd\ sd,ans=3s-9d sdddd sdddd sd,ans=3s−9d 否则输出 D e f i c i t Deficit Deficit.
#include<iostream> #include<string> #include<cstdio> #include<cstring> #include<algorithm> #include<cctype> #include<sstream> #include<set> #include<cmath> #include<cstdlib> #include<vector> typedef long long ll; using namespace std; int main(){ ll s,d,ans; while(cin>>s>>d){ ans=-1; if(d>4*s) ans=10*s-2*d; else if(2*d>3*s) ans=8*s-4*d; else if(3*d>2*s) ans=6*s-6*d; else if(4*d>s) ans=3*s-9*d; else ans=-1; if(ans>0) printf("%d\n",ans); else puts("Deficit"); } return 0; }这是一个经典的后效性贪心问题,即前面的选择会对后面的结果产生影响,因此前面如何选择贪心就是关键.
