poj 3666 Making the Grade （动态规划）

本文主要是介绍poj 3666 Making the Grade （动态规划），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

菜菜的说一下（若有幸被高人看见，请指导），初次学dp，这个题想了好久，不会~上网看了一个思路，看了好久，终于看懂了~ 好笨啊%>_<%

 

先附此人博客：

http://blog.sina.com.cn/s/blog_82a8cba50100tog6.html

 

题意：输入N, 然后输入N个数，求最小的改动这些数使之成非严格递增即可，要是非严格递减，反过来再求一下就可以了。

 

看了有些报告，离散化~不太懂。但是我看懂的那个思路是这样：dp[i][j] = min(dp[i-1][k])+a[i]-b[j], 1<=k<=j。dp[i=当前考虑的前i个数][j=第i个数在总序列中排第j小]=当前的情况的最小改动量。什么意思呢，就是求当前dp[i][j]时候，考虑前i-1个数字，取第i-1个数字在第k（k=1…j）小中的最小改动量，再加上第i个数字成为第j小的改动量。 开始我不太懂，然后在纸上逐个手动推，才略知了。后来又根据此人的后续思路把二维dp给成用滚动数组替代，空间复杂度刷成了200k+。

 

附代码：

 

#include "stdio.h"
#include "iostream"
#include "algorithm"
using namespace std;
__int64 dp[2][2003];
int main()
{
freopen("aaa.txt","r",stdin);
__int64 m,temp;
__int64 a[2003],b[2003];
int n,i,j;
while(scanf("%d",&n)!=EOF)
{
for(i=1; i<=n; i++)
scanf("%I64d",&a[i]), b[i]=a[i];
sort(b+1,b+n+1);
for(i=1; i<=n; i++)
{
dp[1][i] = a[1]-b[i];
if(dp[1][i]<0)  dp[1][i]=-dp[1][i];
}
for(i=2; i<=n; i++)
{
temp=dp[(i+1)%2][1];
for(j=1; j<=n; j++)
{
temp=min(temp,dp[(i+1)%2][j]);
m=a[i]-b[j];
if(m<0)  m=-m;
dp[i%2][j]=temp+m;
}
}
temp=dp[n%2][n];
for(i=n; i>=1; i--)
temp = min(temp,dp[n%2][i]);
printf("%I64d\n",temp);
}
return 0;
}

这篇关于poj 3666 Making the Grade （动态规划）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---