洛谷 P1220 关路灯

我递推啥都不会写垃圾死了,一道对我来说用递推非常难以解决的、难以思考的DP题目被我用记忆化递归解决了,0ms,高兴死我啦!
哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈,代码写的那么长。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<cstring>
using namespace std;
int n,c;
int pos[55],power[55];
int prefixPower[55];
int f[55][55][2];
inline int getEnergy(int l,int r){
    return prefixPower[n]-prefixPower[r]+prefixPower[l-1];
}
int dp(int l,int r,int d){
    if(f[l][r][d]!=-1)return f[l][r][d];
    if(l==1&&r==n)return f[l][r][d]=0;
    if(l==1&&r<n)return f[l][r][d]=getEnergy(l,r)*(d?pos[r+1]-pos[r]:pos[r+1]-pos[l])+dp(l,r+1,1);
    if(l>1&&r==n)return f[l][r][d]=getEnergy(l,r)*(d?pos[r]-pos[l-1]:pos[l]-pos[l-1])+dp(l-1,r,0);
    else return f[l][r][d]=min(getEnergy(l,r)*(d?pos[r]-pos[l-1]:pos[l]-pos[l-1])+dp(l-1,r,0),getEnergy(l,r)*(d?pos[r+1]-pos[r]:pos[r+1]-pos[l])+dp(l,r+1,1));
}
int main(){
    ios::sync_with_stdio(false);
    memset(f,-1,sizeof(f));
    cin>>n>>c;
    for(int i=1;i<=n;i++)cin>>pos[i]>>power[i];
    for(int i=1;i<=n;i++)prefixPower[i]=prefixPower[i-1]+power[i];
    cout<<min(dp(c,c,0),dp(c,c,1));
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注