转化为括号序列DP
注意边界
#include<cstdio>
#include<algorithm>
#define rep(i,x,y) for (int i=x; i<=y; i++)
using namespace std;
long long F[3005][3005];
int main(){
int n,T;
scanf("%d%d",&n,&T);
rep(i,0,n) rep(j,0,n+1) F[i][j]=1ll<<60;
F[0][0]=0;
for (int i=1; i<=n; i++){
int u,v,d,e;
scanf("%d%d%d%d",&u,&v,&d,&e);
for (int j=0; j<=n; j++) F[i][j]=min(F[i][j],F[i-1][j]+u+v);
for (int j=1; j<=n; j++) F[i][j]=min(F[i][j],F[i-1][j]+e+d);
for (int j=1; j<=n; j++) F[i][j]=min(F[i][j],F[i-1][j-1]+d+v);
for (int j=0; j<=n; j++) F[i][j]=min(F[i][j],F[i-1][j+1]+u+e);
for (int j=1; j<=n; j++) F[i][j]=min(F[i][j],F[i][j-1]+d+v);
for (int j=n; j>=0; j--) F[i][j]=min(F[i][j],F[i][j+1]+u+e);
for (int j=0; j<=n; j++) F[i][j]+=2*j*T;
}
printf("%lld
",F[n][0]+(n+1)*T);
return 0;
}