洛谷$1220$ 关路灯记搜/$DP$

$Sol$

约定$pos$为老张所处的位置的路灯号,$i<pos,j>pos$.

显然,如果$i$和$j$都关了,那么它们之间的所有灯一定也都关了.

设$f[i][j][k]$表示关掉$[i,j]$的灯,现在在$k$位置($k=i$或$k=j$),所有路灯的功耗.

转移有两种,显然,懒得写了.

记搜即可.

$Code$

写得挺复杂的,感觉都可以评上最长代码了.

#include<bits/stdc++.h>

#define il inline

#define Ri register int

#define go(i,a,b) for(Ri i=a;i<=b;++i)

#define yes(i,a,b) for(Ri i=a;i>=b;--i)

#define e(i,u) for(Ri i=b[u];i;i=a[i].nt)

#define mem(a,b) memset(a,b,sizeof(a))

#define ll long long

#define db double

#define inf 2147483647

using namespace std;

il int read()

{

    Ri x=0,y=1;char c=getchar();

    while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();}

    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}

    return x*y;

}

const int N=60;

int n,c,sw[N],s[N],as,rem[N][N][N];

struct nd{int p,w;}a[N];

il int sol(Ri l,Ri r,Ri p)

{

    Ri ret=0;

    if(rem[l][r][p])return rem[l][r][p];

    if(l==c)

    {

	    go(i,l+1,r)ret+=s[i];;ret+=(sw[n]-(sw[r]-sw[l-1]))*(a[r].p-a[l].p);

	    if(p==c)ret+=(sw[n]-(sw[r]-sw[l-1]))*(a[r].p-a[l].p);

	    return rem[l][r][p]=ret;

    }

    if(r==c)

    {

	    go(i,l,r-1)ret+=s[i];;ret+=(sw[n]-(sw[r]-sw[l-1]))*(a[r].p-a[l].p);

	    if(p==c)ret+=(sw[n]-(sw[r]-sw[l-1]))*(a[r].p-a[l].p);

	    return rem[l][r][p]=ret;

    }

    if(p==l)

    {

	    ret=sol(l+1,r,l+1)+(sw[n]-(sw[r]-sw[l]))*(a[l+1].p-a[l].p);

	    ret=min(ret,sol(l+1,r,r)+(sw[n]-(sw[r]-sw[l]))*(a[r].p-a[l].p));

    }

    else

    {

	    ret=sol(l,r-1,l)+(sw[n]-(sw[r-1]-sw[l-1]))*(a[r].p-a[l].p);

	    ret=min(ret,sol(l,r-1,r-1)+(sw[n]-(sw[r-1]-sw[l-1]))*(a[r].p-a[r-1].p));

    }

    return rem[l][r][p]=ret;

}

int main()

{

    n=read(),c=read();

    go(i,1,n)

	a[i]=(nd){read(),read()},sw[i]=sw[i-1]+a[i].w;

    go(i,1,n)s[i]=abs(a[i].p-a[c].p)*a[i].w;

    as=min(sol(1,n,1),sol(1,n,n));

    printf("%d\n",as);

    return 0;

}

巴特西

洛谷$1220$ 关路灯记搜/$DP$

\(Sol\)

\(Code\)

最新文章

热门文章

巴特西

洛谷$1220$ 关路灯 记搜/$DP$

\(Sol\)

\(Code\)

最新文章

热门文章

洛谷$1220$ 关路灯记搜/$DP$