dalao求助一波，有头绪at我，谢谢dalao

题目:P1220 关路灯

CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define ll long long
#define MAXN 55

ll n , c , s[MAXN] , w[MAXN] , dp[MAXN][MAXN][MAXN] , p[MAXN];
// dp的三维分别表示  左区间  右区间  这段区间中开始的地方

int main()
{
	memset (dp , 0x3f , sizeof dp);
	cin >> n >> c;
	for(int i = 1 ; i <= n ; i ++)
	{
		cin >> s[i] >> w[i];
		p[i] = p[i-1] + w[i];
	}
	
	for(int i = 1 ; i <= n ; i ++) dp[i][i][i] = 0; // 初始
	
	for(int len = 2 ; len <= n ; len ++) // Length
	{
		for(int i = 1 ; i <= n - len + 1 ; i ++) // Left
		{	
			int j = len + i - 1; // Right
			for(int k = i ; k < j ; k ++) // 断点
			{
				for(int be = i ; be <= j ; be ++) // 开始处
				{
					if(be <= k) // 开始的在断点左边
					{
						dp[i][j][be] = min (dp[i][j][be] , dp[i][k][be] + dp[k+1][j][k+1] + (s[k+1] + s[be] - s[i] - s[i]) * (p[j] - p[k]));
						// 开始处转移到左边,那么跑完左边后就会到右边的最左端点（k+1），再加上 跑的时间（具体开始跑到最左边，再跑到右边开始）*右边功率和
						
//						printf("T2>dp[i = %d][k = %d][be = %d]=%lld  dp[k+1 = %d][j = %d][k+1 = %d]=%lld  s[k+1 = %d]+s[be = %d]-2*s[i = %d]=%lld  p[j = %d]-p[k = %d]=%lld\n",i,k,be,dp[i][k][be],k+1,j,k+1,dp[k+1][j][k+1],k+1,be,i,s[k+1] + s[be] - s[i] * 2,j,k,p[j]-p[k]);
					}
					else { // 断点在右边
						dp[i][j][be] = min (dp[i][j][be] , dp[i][k][k] + dp[k+1][j][be] + (s[j] + s[j] - s[k] - s[be]) * (p[k] - p[i-1]));
						// 转移同上
						
//						printf("T3>dp[i = %d][k = %d][k = %d]=%lld  dp[k+1 = %d][j = %d][be = %d]=%lld  2*s[j = %d]-s[k = %d]-s[be = %d]=%lld  p[k = %d]-p[i-1 = %d]=%lld\n",i,k,k,dp[i][k][k],k+1,j,be,dp[k+1][j][be],j,k,be,2*s[j]-s[k]-s[be],k,i-1,p[k]-p[i-1]);
					}	
					
//					printf("Test_1 --> i = %d  j = %d  k = %d  be = %d  dp[%d][%d][%d] = %lld\n",i,j,k,be,i,j,be,dp[i][j][be]);
//					cout << endl;
				}
			}
		}
	}
	
	cout << dp[1][n][c];
	
	return 0;
}

有一些注释是调试，个人感觉转移没有出问题，谢谢大佬啦！

s数组表示坐标，w数组表示每个路灯的功率，p表示功率前缀和