锐客网

  1. 首页 > it技术 > >

poj 3666 Making the Grade （动态规划）

dp

菜菜的说一下（若有幸被高人看见，请指导），初次学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+。

【poj 3666 Making the Grade （动态规划）】附代码：

#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; }



    推荐阅读


    上一篇：关于#include|关于#include ＂stdafx.h＂

    下一篇：java|java中URL的应用