题解 P1376 【机器工厂】
Ryan_
2019-09-29 09:38:31
一道普及题，看来是自己想太多了
一开始的贪心策略是
第一周直接计算答案就好
若往后的一周保养费乘以第一周的所有订单比
往后的那一周还要小的话我们即考虑在第一周
就买好第二周需要的货，否则就不买
如果第一周囤货确实时价格更少了
那么我们就考虑第三周该不该囤货，以及实在第一周囤货
还是在第二周囤货以此类推
注意：被cut掉的方案永远不会再用，因为越往后性价比
只可能越劣，所以前面的方案肯定比后面（cut掉）的方案劣
于是最高70分，想了想大仙自己没有考虑到，随着i的增大，原本更优的方案，可能会比原本更劣的（已经cut掉的）方案更劣
**30分代码**
```
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int long long n,s,ans=0;
struct object{
int cost,sale;
}a[10001];
int main(){
scanf("%d%d",&n,&s);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].cost,&a[i].sale);
}
ans+=a[1].cost*a[1].sale;
int flag=1;
for(int i=2;i<=n;i++){
if(a[flag].cost*(i-flag)*s*a[i].sale<a[i].cost*a[i].sale){
ans+=a[flag].cost*((i-flag)*s*a[i].sale);
if(a[flag].cost*(i-flag+1)*s*a[i+1].sale>=a[i].cost*s*a[i+1].sale){
flag=i;
}
}
else {
flag=i;
ans+=a[flag].cost*a[flag].sale;
}
}
printf("%d",ans);
return 0;
}
```
**60分代码**
```
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int long long n,s,ans=0;
struct object{
int cost,sale;
}a[10001];
int main(){
scanf("%d%d",&n,&s);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].cost,&a[i].sale);
}
ans+=a[1].cost*a[1].sale;
int flag=1;
for(int i=2;i<=n;i++){
if(a[flag].cost*a[i].sale+(i-flag)*s*a[flag].sale<a[i].cost*a[i].sale){
ans+=a[flag].cost*a[i].sale+((i-flag)*s*a[i].sale);
if(a[flag].cost*a[i+1].sale+(i-flag+1)*s*a[i+1].sale>=a[i].cost*s*a[i+1].sale){
flag=i;
}
}
else {
flag=i;
ans+=a[flag].cost*a[flag].sale;
}
}
printf("%d",ans);
return 0;
}
```
**70分代码**
```
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int long long n,s,ans=0;
struct object{
int cost,sale;
}a[100001];
int main(){
scanf("%lld%lld",&n,&s);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&a[i].cost,&a[i].sale);
}
ans+=a[1].cost*a[1].sale;
int flag=1;
for(int i=2;i<=n;i++){
if(a[flag].cost*a[i].sale+(i-flag)*s*a[flag].sale<a[i].cost*a[i].sale){
ans+=a[flag].cost*a[i].sale+((i-flag)*s*a[i].sale);
if(a[flag].cost*a[i+1].sale+(i-flag+1)*s*a[i+1].sale>=a[i].cost*s*a[i+1].sale){
flag=i;
}
}
else {
flag=i;
ans+=a[flag].cost*a[flag].sale;
}
}
printf("%lld",ans);
return 0;
}
```
100分代码
```
#include<bits/stdc++.h>
using namespace std;
long long minn(int long long a,int long long b){
if(a<b)return a;
else return b;
}
int main(){
int long long last,n,s,ans=0;
cin>>n>>s;
for(int i=1,a,b;i<=n;i++){
cin>>a>>b;
if(i==1)last=a;
else last=minn(last+s,a);
ans+=last*b;
}
cout<<ans;
return 0;
}
```