卡车更新问题

问题描述 Problem Description

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

输入描述 Input Description

第 1 行: N (运输户工作年限)
第 2 行: k (卡车最大使用年限, k≤20 )
第 3 行: R0 R1 ... Rk
第 4 行: U0 U1 ... Uk
第 5 行: C0 C1 ... Ck

输出描述 Output Description

第 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

分析 I Think

题目已经把状态转移方程差不多都给了…

代码 Code

#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;

const double eps = 1E-8;

double r[22],u[22],c[22];
double f[22][22];
int n,k;

void display(int,int);

int main(){

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]);
    r[k+1] = -1E20;
    u[k+1] = c[k+1] = 1E20;

for(int i=0;i<=n;++i)
for(int j=0;j<=k;++j)
            f[i][j] = -1E20;

    f[1][1] = r[0]-u[0];
for(int i=1;i<n;++i)
for(int j=1;j<=k;++j){
            f[i+1][j+1] = max(f[i+1][j+1],f[i][j]+r[j]-u[j]);
            f[i+1][1] = max(f[i+1][1],f[i][j]+r[0]-u[0]-c[j]);
        }

double ans = -1E20;
int p;
for(int i=0;i<=k;++i)
if(ans < f[n][i]){
            ans = f[n][i];
            p = i;
        }

printf("%.1lf\n",ans);
    display(n,p);

return 0;

}

void display(int p,int q){

if(p == 1){
printf("1 0 %.1lf\n",f[1][1]);
return ;
    }

if(q == 1)
for(int i=1;i<=k;++i)
if(fabs(f[p-1][i]+r[0]-u[0]-c[i]-f[p][q]) < eps){
                display(p-1,i);
printf("%d 1 %.1lf\n",p,r[0]-u[0]-c[i]);
return ;
            }

    display(p-1,q-1);
printf("%d 0 %.1lf\n",p,r[q-1]-u[q-1]);

}

秒客网