BZOJ 4244スタンプラリー
タイトル:
考え方:
ブログ参照
https://blog.csdn.net/forever_shi/article/details/84931438
考え方:
ブログ参照
https://blog.csdn.net/forever_shi/article/details/84931438
/**************************************************************
Problem: 4244
User: fufck
Language: C++
Result: Accepted
Time:8364 ms
Memory:72076 kb
****************************************************************/
#include
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=b;i>=a;i--)
using namespace std;
#define ll long long
const int N=3e5+5;
const int mod = 998244353;
ll rd()
{
ll x=0,f=1;char ch=getchar();
while(ch'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,T,u,v,d,e;
ll f[3010][3010];
int main()
{
n=rd();T=rd();
memset(f,0x3f,sizeof(f));
f[0][0]=0;
rep(i,1,n)
{
u=rd(); v=rd();d=rd();e=rd();
rep(j,1,n) f[i-1][j]+=2*T*j;
rep(j,1,n) f[i][j]=min(f[i][j],f[i-1][j-1]+d+v);
rep(j,0,n-1) f[i][j]=min(f[i][j],f[i-1][j+1]+e+u);
rep(j,0,n) f[i][j]=min(f[i][j],f[i-1][j]+u+v);
rep(j,1,n) f[i][j]=min(f[i][j],f[i-1][j]+d+e);
rep(j,1,n) f[i][j]=min(f[i][j],f[i][j-1]+d+v);
dep(j,0,n-1) f[i][j]=min(f[i][j],f[i][j+1]+u+e);
}
printf("%lld
",f[n][0]+1ll*(n+1)*T);
}