卡车更新问题

时间：2021-03-06 20:40:20

卡车更新问题

Description

某人购置了一辆新卡车, 从事个体运输业务. 给定以下各有关数据: R[t],t=0，1,2,...,k , 表示已使用过 t 年的卡车, 再工作一年所得的运费, 它随 t 的增加而减少, k ( k≤20 ) 年后卡车已无使用价值.
U[t]：t=0，1,...,k , 表示已使用过 t 年的卡车, 再工作一年所需的维修费, 它随 t 的增加而增加.
C[t]：t=0，1,2,...,k , 表示已使用过 t 年的旧卡车, 卖掉旧车, 买进新车, 所需的净费用, 它随 t 的增加而增加.
以上各数据均为实型, 单位为”万元”.
设某卡车已使用过 t 年,
① 如果继续使用, 则第 t+1 年回收额为 R[t]−U[t] ,
② 如果卖掉旧车,买进新车, 则第 t+1 年回收额为 R[0]−U[0]−C[t] .
该运输户从某年初购车日起,计划工作 N(N<=20) 年, N 年后不论车的状态如何,不再工作.
为使这 N 年的总回收额最大, 应在哪些年更新旧车? 假定在这N年内, 运输户每年只用一辆车, 而且以上各种费用均不改变.

Input

第 1 行: N (运输户工作年限)
第 2 行: k (卡车最大使用年限, k≤20 )
第 3 行: R[0] R[1] ... R[k]
第 4 行: U[0] U[1] ... U[k]
第 5 行: C[0] C[1] ... C[k]

Output

第 1 行: W ( N 年总回收额)
第 2 – N+1 行: 每行输出 3 个数据:
年序号 ( 从 1 到 N 按升序输出);
否更新 ( 当年如果更新,输出 1 , 否则输出 0 );
当年回收额 ( N 年回收总额应等于 W ).

Sample Input

4
5
8 7 6 5 4 2
0.5 1 2 3 4 5
0 2 3 5 8 10

Sample Output

24.5
1 0 7.5
2 1 5.5
3 1 5.5
4 0 6.0

Solution

设 fi,j 第 i 年使用的卡车年限为 j 的最大回收额。
若 j=1 表示它去年更新了，则 fi,j=Max{fi−1,k+r[0]−u[0]−c[k]}
否则 fi,j=fi−1,j−1+r[j−1]−u[j−1]

Code

#include <iostream>
#include <cstdio>
#include <cfloat>

#define Max(x,y) ((x)>(y)?(x):(y))
#define Min(x,y) ((x)<(y)?(x):(y))

using namespace std;

int n,k;

double r[30],u[30],c[30],f[100000][30];
int g[100000][30];
double ans=DBL_MIN;

void work(int year,int x){
if(year==1)return;
    work(year-1,g[year][x]);
if(x==1)printf("%d %d %.1lf\n",year,1,f[n][x]-f[n-1][g[year][x]]);
else printf("%d %d %.1lf\n",year,0,f[n][x]-f[n-1][g[year][x]]);
}

int main(){

    freopen("truck.in","r",stdin);
    freopen("truck.out","w",stdout);

memset(f,0xc2,sizeof f);
double oo=f[0][0];

scanf("%d%d",&n,&k);
for(int i=0;i<=k;i++)scanf("%lf",&r[i]);
for(int i=0;i<=k;i++)scanf("%lf",&u[i]);
for(int i=0;i<=k;i++)scanf("%lf",&c[i]);

    f[1][1]=r[0]-u[0];
for(int i=2;i<=n;i++){
for(int j=1;j<=k;j++){
if(j==1){
for(int l=1;l<=k;l++)
if(f[i-1][l]!=oo){
if(f[i-1][l]+r[0]-u[0]-c[l]>f[i][j]){
                            f[i][j]=f[i-1][l]+r[0]-u[0]-c[l];
                            g[i][j]=l;
                        }
                    }
            }
else{
if(f[i-1][j-1]!=oo){
                    f[i][j]=f[i-1][j-1]+r[j-1]-u[j-1];
                    g[i][j]=j-1;
                }
            }
        }
    }
int ttt;
for(int i=0;i<=k;i++){
if(f[n][i]>ans){
            ans=f[n][i];
            ttt=i;
        }
    }
printf("%.1lf\n",ans);
printf("%d %d %.1lf\n",1,0,r[0]-u[0]);
    work(n,ttt);
return 0;
}
标签：

相关文章