一個字貪,第一天,只能選擇制作方式,后面的每一天,在<今天制作>與<前期存儲>之間取更優解
例如樣例:100 5,200 5,90 20,存儲成本為10
第1天:
一定是制作,成本為100*5=500,此時最優單價為100
第2天:
如果還是制作,單價為200。如果選擇存儲,單價為100+10,相比較,選擇存儲方式更有性價比。所以選擇存儲,成本為(100+10)5=550,此時最優單價為110
第3天:
如果選擇制作,單價為90。如果選擇存儲,單價為110+10,相比較,選擇制作更有性價比。所以選擇制作,成本為9020=1800。
最終成本=500+550+1800
#include<iostream>
int main(){int n,s;std::cin>>n>>s;long long min,c,a;std::cin>>min>>a;//first daylong long sum=0;sum+=min*a;for(int i=1;i<n;++i){min+=s;std::cin>>c>>a;if(min>c)min=c;sum+=min*a;}std::cout<<sum<<"\n";
}