P1103书本整理_C_内存溢出

一、题目

二、解题思路

1.首先需要将书根据高进行排序。发现书的高度唯一，因此我们可以采用map进行书的存储，存储完毕后，书将会自动有序。
2.考虑到前面的书拿掉时不会对后面的结果产生影响，因此可以想到该题可用动态规划进行求解。
3.应当注意的是，在动规时，应当保存每本书的状态（第i本书是否保留，因为如果不保留的话，无法计算第i本书以后的不整齐度），此时规定dp[k][i][0]表示对于前i本书，当不保留第i本书时，拿走k本书后的最优值；dp[k][i][1]表示对于前i本书，当保留第i本书时，拿走k本书后的最优值。假设我们未保留每本书的状态，令dp[k][i]表示对于前i本书，拿走k本书后的最优值，显然，此时无法计算dp[k][i+1]的值，因为我们不知道前i本书中，到底哪些书被保留了，那也就无法计算不整齐度。
4.对于dp[k][i][0]的计算，我们只需要关注当前i-1本书中，拿掉k-1本书后的最优值即可，至于第i-1本书是否被拿掉，都不影响最终结果，因为新加的书直接被拿掉，相当于没加。则dp[k][i][0]=min(dp[k-1][i-1][0],dp[k-1][i-1][1])；而对于dp[k][i][1]的计算则稍微复杂点，我们需要找到最近被保留的那本书，才可以计算保留第i本书后，新的不整齐度变为多少，此时可采用遍历的方法，从最靠近i的书开始遍历，值得注意的是，每往前移动一位，拿掉的书应该多一本，具体来说，当我们假设最近保留的书为i-1时，那我们只需要得到dp[k][i-1][1]的结果即可得到此时dp[k][i][1]的结果；当最近保留的书为i-2时，我们需要得到dp[k-1][i-2][1]的结果，而非dp[k][i-2][1]，因为当最近保留的书为i-2时，相当于默认把第i-1本书拿掉了。

三、代码

#include
#include
#include
#include
#include
#include
using namespace std;

int main(){
    int n,k;
    int dp[201][201][2]={0};
    cin>>n>>k;
    map books;
    for(int i=0;i>h>>w;
        books[h]=w;
    }
    vector weights(1, 0);
    map::iterator it=books.begin();
    while(it!=books.end()){
        weights.push_back(it->second);
        it++;
    }
    //初始化动规数组
    int irregularity=0;
    for(int i=2;i<=n;i++){
        irregularity+=abs(weights[i]-weights[i-1]);
        //dp[k][n][0]表示前n个中，当不保留第n本书时，拿掉k本书的最优值
        //dp[k][n][1]表示前n个中，当保留第n本书时，拿掉k本书的最优值
        dp[0][i][1]=irregularity;
    }
    for(int i=2;i<=n;i++){
        dp[1][i][0]=dp[0][i][1]-abs(weights[i]-weights[i-1]);
        dp[1][i][1]=irregularity;
        if(i==2){
            dp[1][i][1]=0;
            continue;
        }
        for(int k=i-1;k>=i-2;k--){
            dp[1][i][1]=min(dp[1][i][1], dp[2-(i-k)][k][1]+abs(weights[i]-weights[k]));
        }
    }
    for(int i=2;i<=k;i++){
    //当j和i的差值小于2时，结果必然为0，因为此时最多只剩下一本书
    for(int j=i+2;j<=n;j++){
        //计算前n个中，当不保留第n本书时，拿掉k本书的最优值
        dp[i][j][0]=min(dp[i-1][j-1][0], dp[i-1][j-1][1]);
        //计算前n个中，当保留第n本书时，拿掉k本书的最优值
        dp[i][j][1]=irregularity;
        for(int k=j-1;k>=j-i-1;k--){
            dp[i][j][1]=min(dp[i][j][1], dp[i-(j-1-k)][k][1]+abs(weights[j]-				weights[k]));
        	}
    	}
	}
	cout<

					
										


					
						欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/langs/791177.html

P1103书本整理

发表评论

评论列表（0条）