最大流既视感

然后

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
      
       #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=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=10000+5;const ll inf=0x3f3f3f3f3f3f3f3f;int n,c;int p[N],s[N];ll dp[2][N];ll ans;int main(){    rd(n);rd(c);    for(reg i=1;i<=n;++i) rd(p[i]);    for(reg i=1;i<=n;++i) rd(s[i]);    int tmp=0;    for(reg i=1;i<=n;++i){        tmp^=1;        memset(dp[tmp],0x3f,sizeof dp[tmp]);        for(reg j=0;j<=i;++j){            if(j) dp[tmp][j]=min(dp[tmp^1][j]+p[i]+(ll)j*c,dp[tmp^1][j-1]+s[i]);            else dp[tmp][j]=dp[tmp^1][j]+p[i]+(ll)j*c;        }    }    ans=inf;    for(reg j=0;j<=n;++j) ans=min(ans,dp[tmp][j]);    cout<
      

思路：

最大流可以想到。但是边数太多

最小割=最大流而且最小割非常直观可以操作，而且网络流的图非常简单有规律

最小割dp就非常合适了。