$n\le 50$很小嘛。
直接搞搞就好了。
不难得知,关灯一定是关一段连续的,因此应该是一个区间。
进而可以从小状态滚到大状态。
由于$n=50$,所以不妨再多一维表示当前位置(实则不用,我太难了
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
using namespace std;
const int N=51;
template<class o>
inline void qr(o &x)
{
x=0;char c=gc;
while(c<'0'||c>'9')c=gc;
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
}
void qw(ll x)
{
if(x/10)qw(x/10);
putchar(x%10+48);
}
ll f[N][N][N];
ll s1[N],s2[N],p[N],w[N];
int main()
{
int n,c;qr(n),qr(c);
for(int i=1;i<=n;i++)
qr(p[i]),qr(w[i]);
for(int i=1;i<=n;i++)s1[i]=s1[i-1]+w[i];
for(int i=n;i;i--)s2[i]=s2[i+1]+w[i];
memset(f,0x3f,sizeof f);f[c][c][c]=0;
for(int k=2;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=i;j<=min(n,i+k-1);j++)
for(int z=i;z<=j;z++)if(f[i][j][z]!=0x3f3f3f3f3f3f3f3f)
{
ll cost=s1[i-1]+s2[j+1];
if(i!=1)f[i-1][j][i-1]=min(f[i-1][j][i-1],f[i][j][z]+(p[z]-p[i-1])*cost);
if(j!=n)f[i][j+1][j+1]=min(f[i][j+1][j+1],f[i][j][z]+(p[j+1]-p[z])*cost);
}
ll ans=f[0][0][0];
for(int z=1;z<=n;z++)ans=min(ans,f[1][n][z]);
qw(ans);puts("");
return 0;
}
最后一次更新于2020-05-13
0 条评论