从lyd蓝书入的门。
一、任务安排1
这是最弱化的板子。
首先考虑O(n3)的DP：f[i][j]=min0<=k<i([f[k][j-1]+(S*J+sumT[i])*(sumC[i]-sumC[k]));
考虑优化：因为没有限制要分成多少批，而我们之所以多设一维j是因为我们需要知道启动了多少次，从而计算时间。
这里运用到一种“费用提前计算”的思想来优化：在DP过程中我们并不容易直接求出每批任务的完成时刻，而我们可以考虑每启动一次就会对之后所有的任务产生影响，
所以我们可以先把费用累加进来，就可以实现O(n2)的DP：f[i]=min0<=j<i{f[j]+sumT[i]*(sumC[i]-sumC[j])+S*(sumC[N]-sumC[j])};
#include<bits/stdc++.h> #define RG register #define IL inline #define LL long long using namespace std; IL int gi () { RG int x=0,w=0; char ch=0; while (ch<‘0‘||ch>‘9‘) {if (ch==‘-‘) w=1;ch=getchar();} while (ch>=‘0‘&&ch<=‘9‘) x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); return w?-x:x; } const int N=1e5+10; int n,S,T[N],C[N]; LL f[N],preT[N],preC[N]; int main () { RG int i,j; n=gi(),S=gi(); for (i=1;i<=n;++i) T[i]=gi(),C[i]=gi(),preT[i]=preT[i-1]+T[i],preC[i]=preC[i-1]+C[i]; memset(f,0x3f,sizeof(f)); f[0]=0; for (i=1;i<=n;++i) for (j=0;j<i;++j) f[i]=min(f[i],f[j]+preT[i]*(preC[i]-preC[j])+S*(preC[n]-preC[j])); printf("%lld\n",f[n]); return 0; }
。。。
原文：https://www.cnblogs.com/Bhllx/p/10360147.html
