https://www.luogu.org/problemnew/show/P1220
题解
对于从第i
个点走到第j
个点,肯定会将[i,j]
的路灯全部关闭。考虑关闭第i+1
个点,现在可能有两种状态,关完[i.j]
之后位于i
,或者位于j
,所以设计状态为dp[i][j][0/1]
代表关完[i.j]
后位于i
或者j
,这样转移就显的很简单了。
预处理路灯功率前缀和,这样可以很方便的算出[i.j]
内的路灯在t
时间内的功率消耗,这也是状态转移的权值。
总的状态转移方程:
dp[i][j][0] = min(dp[i][j][0], dp[i+1][j][0]+w1, dp[i+1][j][1]+w2)
dp[i][j][1] = min(dp[i][j][1], dp[i][j-1][0]+w1, dp[i][j-1][1]+w2)
因为肯定是从小的区间转移到大的区间,所以这和区间dp一样,从小区间枚举到大区间。
代码
#include <bits/stdc++.h>
using namespace std;
#define FOR0(a,b) for(int i = a; i < b; ++i)
#define FORE(a,b) for(int i = a; i <= b; ++i)
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 0x3f3f3f3f;
int dp[55][55][2],n,c;
int a[55], b[55],sum