[dynamic planning] p1220: interval DP: turn off the street lights

Turn off the section 【i,j】 Inside the lamp and at the end on the left （ The first i Turn off the light last ）, This state can be transferred from two states ：

（1） Turn off the section 【i+1,j】 And the end is i+1

          f[i+1][j][0]+d[i,i+1]*p(  p For the power and , That's the interval 【i+1,j】 The sum of numbers beyond , You can use prefixes and preprocessing )

（2） Turn off the section 【i+1,j】 And the end is j

        f[i+1][j][1]+d[i,j]*p

Turn off the section 【i,j】 Inside the lamp and at the end on the right

initialization ：

dp[c][c][0]=dp[c][c][1]=0（0 You can turn it off in seconds c Position light ）

All others are initially INF( Because minimum value is required )

Be careful ：

Algorithm problems are routine problems , Only do more and accumulate more , Only when you see new topics can you have ideas ！

When doing a question , If not , You can see the solution ！

expand ：

Fill in the form ：

Use the state transition equation and the previous state to deduce the state appearing in （ It is equivalent to knowing the known conditions , Fill in the answers ）

Brush table method ：

Take advantage of the current state , Push out the next related state .

Code ：

#include<iostream>
#include<cstring>
using namespace std;
int n,c;
int x[51],p[51],sum[51],dp[51][51][2];
int main(){
	cin>>n>>c;
	sum[0]=0;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>p[i];
		sum[i]=sum[i-1]+p[i];
	}
	memset(dp,0x3f,sizeof(dp));
	dp[c][c][0]=dp[c][c][1]=0;
	for(int i=c;i>=1;i--){
		for(int j=i+1;j<=n;j++){
			dp[i][j][0]=min(dp[i+1][j][0]+(x[i+1]-x[i])*(sum[n]-(sum[j]-sum[i])),dp[i+1][j][1]+(x[j]-x[i])*(sum[n]-(sum[j]-sum[i])));
			dp[i][j][1]=min(dp[i][j-1][0]+(x[j]-x[i])*(sum[n]-(sum[j-1]-sum[i-1])),dp[i][j-1][1]+(x[j]-x[j-1])*(sum[n]-(sum[j-1]-sum[i-1])));
		}
	}
	int res=0x3f;
	res=min(dp[1][n][0],dp[1][n][1]);
	cout<<res;
	return 0; 
	
}