【Kuangbin区间DP】奶牛零食
DP 区间 奶牛
2023-09-11 14:14:52 时间
题意:
写了Kuangbin的三道DP,三道都不会QwQ
是不是该remake了....
思路:
一开始我天真的以为那个题单全是线性DP,然后我就自然而然往线性DP的方向上想了呜呜
我设 dp[i][j]表示阶段 i ,且这个阶段 去掉的数为 j 的最大收益
然后我是这样转移的:
因为第 i 个阶段,我们去枚举状态
这个位置 j 一定在 [1,i] U [n-i+1,n]里面
dp[i][j]=dp[i-1][j-1]+i*a[j] j属于[1,i]
dp[i][j]=dp[i-1][j+1]+i*a[j] j属于[n-i+1,n]
写完还觉得这样非常的对,其实阶段就有问题啊
区间DP的阶段是以区间作为阶段的,而线性DP的阶段是以线性为阶段的
这道题,我们发现一个区间的子问题一定是它的子区间,那肯定是区间DP
然后状态转移就比较易错了
拿掉a[l]之前的收益是该轮的收益+区间[l+1][r]的收益
拿掉a[r]之前的收益是该轮的收益+区间[l][r-1]的收益
Code:
#include <bits/stdc++.h>
using namespace std;
const int mxn=2e3+10;
int n;
int a[mxn],dp[mxn][mxn];
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int len=1;len<=n;len++){
for(int l=1;l+len-1<=n;l++){
int r=l+len-1;
dp[l][r]=max(dp[l+1][r]+a[l]*(n-(r-l)),dp[l][r-1]+a[r]*(n-(r-l)));
}
}
cout<<dp[1][n]<<'\n';
}
总结:
需要有点辨识度吧,以区间为状态那肯定是区间DP
然后写状态转移方程的时候,一定要按照定义来写,不然很容易写寄
相关文章
- 最优矩阵连乘问题 区间DP
- hdu 4745 Two Rabbits 区间dp
- POJ1651 Multiplication Puzzle 区间DP
- 区间DP----模板
- HDU 3681 Prison Break(状态压缩dp + BFS)
- HDU 2089 不要62(数位DP)
- POJ 3280 Cheapest Palindrome(DP 回文变形)
- HDU 3127 WHUgirls(DP 完全背包)
- 2. Using 'dp' instead of 'px' to set text size
- Remember the Word,LA3942(Trie树+DP)
- BZOJ 2878([Noi2012]-失落的游乐园树DP+出站年轮加+后市展望DP+vector的erase)
- 期望DP
- POJ 1651 Multiplication Puzzle 区间dp(水
- HDU4960Another OCD Patient(间隙dp,后座DP)
- uva 1331 - Minimax Triangulation(dp)
- 377. Combination Sum IV——DP本质:针对结果的迭代,dp[ans] <= dp[ans-i] & dp[i] 找三者关系 思考问题的维度+1,除了数据集迭代还有考虑结果
- 900. 整数划分——计数DP