最大流既视感
然后
TLEMLE既视感
然后
最大流=最小割
然后
dp[i][j]前i个点j个点在S集合，最小割
然后
dp[i][j]=min(dp[i-1][j]+p[i]+j*c,dp[i-1][j-1]+s[i])考虑i点和T的边要不要断
然后
滚动数组优化一下，O(n^2)过10000
#include<bits/stdc++.h>
#define reg register int
#define il inline
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){
char ch;x=;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*+numb);
(fl==true)&&(x=-x);
}
namespace Miracle{
const int N=+;
const ll inf=0x3f3f3f3f3f3f3f3f;
int n,c;
int p[N],s[N];
ll dp[][N];
ll ans;
int main(){
rd(n);rd(c);
for(reg i=;i<=n;++i) rd(p[i]);
for(reg i=;i<=n;++i) rd(s[i]);
int tmp=;
for(reg i=;i<=n;++i){
tmp^=;
memset(dp[tmp],0x3f,sizeof dp[tmp]);
for(reg j=;j<=i;++j){
if(j) dp[tmp][j]=min(dp[tmp^][j]+p[i]+(ll)j*c,dp[tmp^][j-]+s[i]);
else dp[tmp][j]=dp[tmp^][j]+p[i]+(ll)j*c;
}
}
ans=inf;
for(reg j=;j<=n;++j) ans=min(ans,dp[tmp][j]);
cout<<ans;
return ;
} }
signed main(){
Miracle::main();
return ;
} /*
Author: *Miracle*
Date: 2018/12/29 14:21:38
*/
思路：
最大流可以想到。但是边数太多
最小割=最大流而且最小割非常直观可以操作，而且网络流的图非常简单有规律
最小割dp就非常合适了。