109、艰苦打工的小蓝2.docx

解题思路

对于环形dp一类的问题，我们有二种解决的方法，一种为?强制连接，另一种为?倍长区间，这里我们用?强制连接?的方式解题。

状态设计及初始化

设]dp[i][j][0/1]?表示当前在?ii?号仓库，已经连续在?j?个仓库工作过，0?表示当前在工厂工作，11?表示当前不在仓库工作。

初始值dp[1][0][0]=dp[1][1][1]=0，其他为?-\inf?inf。

基础转移方程

我们需要从?22?种不同角度考虑dp思路，因此最基础的便是考虑所有仓库是一条直线的方程。即：dp[i][j][0]=max{dp[i?1][j][0],dp[i?1][j][1]}

dp[i][j][1]=max{dp[i?1][j?1][0],dp[i?1][j?1][1]+u[i]}对于不在当前仓库工作，我们可以选择和之前一样继续不工作，或者从之前工作的状态结束。

对于在当前仓库工作，我可以选择从之前不工作转移而来（注意没有酬劳），或者从之前工作状态转移而来。

注意，我们这里选择的是非连续的，所以从小到大枚举即可。

最终结果为max{dp[n][m][0],dp[n][m][1]}。

二次DP转移方程

因为我们这里要强制连接，所有我们在?二次DP，我们的初始化为?dp[1][1][1]=u[1],dp[1][0][0]=0，其余为?-inf。因为这里我们强制连接?nn?号仓库与?11?号仓库。

为什么这样可行呢，因为我们可以选取非连续的部分，也就是说如果我们想选n?1～2，结果便是?n?1～n+n～1+1～2，我们只要把n～1?强制连接在一起即可。

状态转移和?一次DP?一样。

最终答案

此时最终结果为?dp[n][b][1]?与?第一次dp?结果的最大值。

时间复杂度为?O(2?n?m)。

AC_Code

C++

#includebits/stdc++.h

usingnamespacestd;

intdp[2010][2010][2],n,b,u[2010],ans;

intmain(){

scanf(%d%d,n,b);

for(inti=1;i=n;i++)scanf(%d,u+i);

memset(dp,-0x3f,sizeof(dp));

dp[1][1][1]=dp[1][0][0]=0;

for(inti=2;i=n;i++){

dp[i][0][0]=dp[i-1][0][0];

for(intj=1;j=b;j++){

dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]);

dp[i][j][1]=max(dp[i-1][j-1][0],dp[i-1][j-1][1]+u[i]);

}

}

ans=max(dp[n][b][0],dp[n][b][1]);

memset(dp,-0x3f,sizeof(dp));

dp[1][1][1]=u[1];

dp[1][0][0]=0;

for(inti=2;i=n;i++){

dp[i][0][0]=dp[i-1][0][0];

for(intj=1;j=b;j++){

dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]);

dp[i][j][1]=max(dp[i-1][j-1][0],dp[i-1][j-1][1]+u[i]);

}

}

ans=max(ans,dp[n][b][1]);

printf(%d\n,ans);

return0;

}

Java

importjava.util.Scanner;

publicclassMain{

publicstaticvoidmain(String[]args){

Scannerscanner=newScanner(System.in);

intn=scanner.nextInt();

intb=scanner.nextInt();

int[]u=newint[n+1];

for(inti=1;i=n;i++){

u[i]=scanner.nextInt();

}

int[][][]dp=newint