2025年wyh的问题-----状态机+区间dp

科技前沿 • 2025-01-24 20:00 • 阅读 56

大家好，我是讯享网，很高兴认识大家。

wyh的问题-----状态机+区间dp

题目链接

这题感觉算是比较难的区间dp问题了，难点在于看起来像区间dp，但是状态太多，找不到状态转移方程，对于每一个位置可以由右边走过来也可以由左边走过来，因此状态表示为
f[i][j][0]表示i到j已经走过且最后位置在i的最小花费
f[i][j][1]表示i到j已经走过且最后位置在j的最小花费
走的时候时间是一直在走的，所以需要用前缀和把每个区段没关的灯的速率累加起来乘以时间
顾可得状态转移方程为

f[i][j][0]=min(f[i+1][j][0]+(d[i+1]-d[i]) * (s[n]-s[j]+s[i]),f[i+1][j][1]+(d[j]-d[i]) * (s[n]-s[j]+s[i]))

讯享网

f[i][j][1]=min(f[i][j-1][1]+(d[j]-d[j-1])*(s[n]-s[j-1]+s[i-1]),f[i][j-1][0]+(d[j]-d[i])*(s[n]-s[j-1]+s[i-1]))

#include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> using namespace std; const int N=1010; int d[N],w[N]; int s[N]; int f[N][N][2]; //f[i][j][0]表示i到j且最后位置在i的最小花费 //f[i][j][1]表示i到j且最后位置在j的最小花费 int main() { 
    int n; while(cin>>n) { 
    int st; cin>>st; for(int i=1;i<=n;i++) { 
    cin>>d[i]>>w[i]; s[i]=s[i-1]+w[i]; } memset(f,0x3f,sizeof f); f[st][st][0]=f[st][st][1]=0; for(int len=2;len<=n;len++) { 
    for(int i=1;i+len-1<=n;i++) { 
    int j=i+len-1; f[i][j][0]=min(f[i+1][j][0]+(d[i+1]-d[i])*(s[n]-s[j]+s[i]),f[i+1][j][1]+(d[j]-d[i])*(s[n]-s[j]+s[i])); f[i][j][1]=min(f[i][j-1][1]+(d[j]-d[j-1])*(s[n]-s[j-1]+s[i-1]),f[i][j-1][0]+(d[j]-d[i])*(s[n]-s[j-1]+s[i-1])); } } cout<<min(f[1][n][0],f[1][n][1])<<endl; } }

讯享网

2025年wyh的问题-----状态机+区间dp

wyh的问题-----状态机+区间dp

题目链接

相关推荐