1098 专业多方法解答

1.这道题采用动态规划的思想，用f[i]表示完成前i个任务所需的最小费用，用tim[i]表示前i项任务所需的时间，用mon[i]表示前i项任务一共的费用系数。动归式如下：

f[i]=min{f[j-1]+s*(mon[n]-mon[j-1])+

tim[i]*(mon[i]-mon[j-1])|1<=j<=i};

如果在完成第j项任务是启动一次机器，后面的所有任务完成的时刻都要加上s，所以每启动一次机器的费用为s*(mon[n]-mon[j-1])；

如果把第j项任务和第i项任务和在一起做，则它们的完成时刻为tim[i]，所以费用为tim[i]*(mon[i]-mon[j-1])。

得分：100

时间复杂度：O(N^2)

空间复杂度：O(5*N)

#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
int f[5001],g[5001];
int len,wei,n,tim[5001],mon[5001],ti[5001],s;
int main(){    
scanf("%d%d",&n,&s);    
for(int b=1;b<=n;++b)
    {        
        scanf("%d%d",&tim[b],&mon[b]);
        tim[b]+=tim[b-1];
        mon[b]+=mon[b-1];
        f[b]=2147483647;
    }   
        for(int i=1;i<=n;++i)        
        for(int j=1;j<=i;++j)
        f[i]=min(f[i],f[j-1]+s*(mon[n]-mon[j-1])+tim[i]*(mon[i]-mon[j-1]));    
        printf ("%d",f[n]);    
        return 0;
}

2.单调队列优化DP，可以做到On

···

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int f[5001],t[5001],que[5001],dp[5001];
int hd,tl,n,s;
int main(){    
scanf("%d%d",&n,&s);    
for(int i=1;i<=n;++i)
    {        
        scanf("%d%d",&t[i],&f[i]);
        t[i]+=t[i-1];
        f[i]+=f[i-1];
    }   
    memset(dp,0x3f,sizeof dp);
    dp[0]=0;hd=0;tl=0;
    que[hd]=0;    
    for(int i=1;i<=n;++i)
    {        
        while(hd<tl&&dp[que[hd+1]]-dp[que[hd]]<=(s+t[i])*(f[que[hd+1]]-f[que[hd]])) hd++;
        dp[i]=min(dp[i],dp[que[hd]]+(f[i]-f[que[hd]])*t[i]+s*(f[n]-f[que[hd]]));        
        while(hd<tl&&(dp[i]-dp[que[tl]])*(f[que[tl]]-f[que[tl-1]])<=(dp[que[tl]]-dp[que[tl-1]])*(f[i]-f[que[tl]])) tl--;
        que[++tl]=i;
    }    
        printf("%d\n",dp[n]);
}

···