题解 P1220 【关路灯】

区间DP, 考虑设\(dp[i][j][t]\)为已经关掉了\([i,j]\)的电灯, 人在t端点处时的最小代价

可以推出方程:

\[dp[i+1][j][0]+(p[n]-p[j]+p[i])*(loc[i+1]-loc[i]) -> dp[i][j][0]
\]

\[dp[i][j-1][0]+(p[n]-p[j-1]+p[i-1])*(loc[j]-loc[i]) -> dp[i][j][1]
\]

\[dp[i][j-1][1]+(p[n]-p[j-1]+p[i-1])*(loc[j]-loc[j-1]) -> dp[i][j][1]
\]

\[dp[i+1][j][1]+(p[n]-p[j]+p[i])*(loc[j]-loc[i]) -> dp[i][j][0]
\]

直接DP... 且慢, 顺序是什么...... 好像很麻烦的样子......

但是其实可以不用考虑顺序问题的, 一位超强的选手\(wyx\)说过:

\(\text{「记忆化搜索, 就是用来解决这种顺序有关的DP的」}\)

如果采用记忆化搜索, 啥都不用想一顿码, 码完AC, 极其快乐, 比那些DP不知道高到哪里去了

code:

#include<bits/stdc++.h>

using namespace std; /*Copyright [tyqtyq](http://oiertyq.github.io). All rights served.*/

#define f(i,x,y) for(int i=x,i##end=y;i<=i##end;++i)

#define d(i,x,y) for(int i=x,i##end=y;i>=i##end;--i)

#define ri register int

#define ll long long

#define il inline

namespace intio{char ch; int read(){ ri x=0,f=1; while(!isdigit((ch=getchar()))) f=ch=='-'?-1:1; while(isdigit(ch)) x=x*10+ch-'0', ch=getchar(); return x*f; } void read(int& x) {x = read();}}; using namespace intio;

int max(int x, int y) {return x>y?x:y;} int min(int x, int y) {return x<y?x:y;}

#define _ 100

int loc[_], p[_];

int dp[_][_][2] ;

int n, c;

// dp[i][j][t]: 已经关掉了[i,j]的电灯, 人在t端点处

// dp[i+1][j][0]+(p[n]-p[j]+p[i])*(loc[i+1]-loc[i]) -> dp[i][j][0]

// dp[i][j-1][0]+(p[n]-p[j-1]+p[i-1])*(loc[j]-loc[i]) -> dp[i][j][1]

// dp[i][j-1][1]+(p[n]-p[j-1]+p[i-1])*(loc[j]-loc[j-1]) -> dp[i][j][1]

// dp[i+1][j][1]+(p[n]-p[j]+p[i])*(loc[j]-loc[i]) -> dp[i][j][0]

void work(int i,int j){

	if(i>j) return ;

	if(dp[i+1][j][0]==0x3f3f3f3f) work(i+1, j);

	if(dp[i][j-1][0]==0x3f3f3f3f) work(i, j-1);

	dp[i][j][0] = min(dp[i+1][j][0]+(p[n]-p[j]+p[i])*(loc[i+1]-loc[i]), dp[i+1][j][1]+(p[n]-p[j]+p[i])*(loc[j]-loc[i]));

	dp[i][j][1] = min(dp[i][j-1][0]+(p[n]-p[j-1]+p[i-1])*(loc[j]-loc[i]), dp[i][j-1][1]+(p[n]-p[j-1]+p[i-1])*(loc[j]-loc[j-1]));

}

int main(){

	memset(dp, 0x3f, sizeof(dp)) ;

	scanf("%d%d",&n,&c) ;

	f(i,1,n) scanf("%d%d", &loc[i], &p[i]), p[i] += p[i-1] ;

	dp[c][c][1] = dp[c][c][0] = 0 ;

	work(1,n);

	cout<<min(dp[1][n][1], dp[1][n][0]) ;

	return 0;

}

巴特西

题解 P1220 【关路灯】

最新文章

热门文章