环形DP

环形DP

  在给定数据是环形数组时，我们求解时要将环形变化为线性数组求解，这里有两种常用的变换方式，下面通过例题给出。

例题1

  通过对某些特殊位置进行不同初始化，多次DP求解最优解。
  休息时间

//环形DP
//通过一定的手段将环形DP转化为线性DP的问题
//本题通过两次DP和错位补充的手段来解决问题
#include
using namespace std;int main(){int n;int b;scanf("%d %d",&n,&b);int val[n];for(int i=0;i<n;i++)scanf("%d",&val[i]);int dp[2][b+1][2];//很好的一种设计滚动数组的方法，这里通过多添加一维的方式，避免阶段递推顺序的改变//我们要巧用位运算，来实现快速的0,1变化。memset(dp,128,sizeof(dp));//很好的一种初始化为最小值的方法，值的学习，哈哈dp[1][0][0]=0;dp[1][1][1]=0;for(int i=2;i<=n;i++){for(int j=0;j<=min(i,b);j++){dp[i&1][j][0]=max(dp[(i&1)^1][j][0],dp[(i&1)^1][j][1]);if(j)dp[i&1][j][1]=max(dp[(i&1)^1][j-1][0],dp[(i&1)^1][j-1][1]+val[i-1]);}}int ans=max(dp[n&1][b][1],dp[n&1][b][0]);memset(dp,128,sizeof(dp));dp[1][1][1]=val[0];for(int i=2;i<=n;i++){for(int j=0;j<=min(i,b);j++){dp[i&1][j][0]=max(dp[(i&1)^1][j][0],dp[(i&1)^1][j][1]);if(j)dp[i&1][j][1]=max(dp[(i&1)^1][j-1][0],dp[(i&1)^1][j-1][1]+val[i-1]);}}ans=max(ans,dp[n&1][b][1]);cout<<ans<<endl;return 0;}

  分析
  本题中有两个技巧是值得学习的，第一个是如何使用memset初始化数组，这里我们只需要知道一下几种初始化方案即可：

1. memset(dp,0,sizeof(dp))：全部初始化为0；
2. memset(dp,-1,sizeof(dp))：全部初始化为-1；
3. memset(dp,128,sizeof(dp))：全部初始化为最小负数；
4. memset(dp,0x3f,sizeof(dp))：全部初始化为memset可以初始化的最大正数；

  第二点技巧是滚动数组的使用，传统的方式中，我们通过一维数组复用的方式来节省空间，但是这种方式需要我们注意递推的细节，一面覆盖之后用到的值，而这里我们采用位运算+数组压缩的方式来实现滚动数组，这里的数组并没有直接压缩为1维，而是保留两行，通过位运算来实现交替使用，进而避免对dp顺序的调整。

例题2

  倍增数组，将环形DP变成线性DP问题；
  环路运输

//倍增方式实现环形DP转化线性DP的第二种方式
#include
using namespace std;int main(){int n;scanf("%d",&n);int arr[2*n];for(int i=0;i<n;i++)scanf("%d",&arr[i]);//似乎都用不到DP啊//只需要单调队列优化即可for(int i=n;i<2*n;i++){arr[i]=arr[i-n];}//for(int i=0;i<2*n;i++)cout<deque<int> deq;int dp[2*n];memset(dp,0,sizeof(dp));for(int i=0;i<2*n;i++){if(i<n/2){for(;!deq.empty()&&arr[i]-i>arr[deq.front()]-deq.front();deq.pop_front());deq.push_front(i);continue;}//单调队列规定动作，屁股维持当前最优值，要判断边界合法性for(;!deq.empty()&&deq.back()<i-n/2;deq.pop_back());dp[i]=max(dp[i-1],arr[i]+i+arr[deq.back()]-deq.back());//cout<//队头根据当前插入的值，将不可能的值弹出，也即剪枝for(;!deq.empty()&&arr[i]-i>arr[deq.front()]-deq.front();deq.pop_front());deq.push_front(i);}cout<<dp[2*n-1]<<endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！