首页 > 其他 > 详细

[2016-03-28][POJ][3666][]Making the Grade]

时间:2016-04-01 23:15:49      阅读:409      评论:0      收藏:0      [点我收藏+]
  • 时间:2016-03-28 17:23:08 星期一

  • 题目编号:[2016-03-28][POJ][3666][]Making the Grade]

  • 分析:dp[i][j]表示把改到第i个数,且把a[i]改成b[i]需要的最少代价,已知b[j]递增,dp[i][j]由dp[i - 1][k]递推过来,如果改成非增,那么就要求 a[j] <= a[k],所以dp[i][j] = min(dp[i - 1][k] + d) k < j;

    1. #include <algorithm>
    2. #include <cstring>
    3. #include <cstdio>
    4. using namespace std;
    5. const int maxn = 2000 + 10;
    6. int a[maxn],b[maxn],n;
    7. int dp[maxn][maxn];
    8. bool cmp(int x,int y){
    9. return x > y;
    10. }
    11. int main(){
    12. scanf("%d",&n);
    13. for(int i = 0;i < n ; ++i){
    14. scanf("%d",&a[i]);
    15. }
    16. memcpy(b,a,sizeof(int) * (n + 1));
    17. sort(b,b + n);
    18. memset(dp,0x7f,sizeof(dp));
    19. for(int i = 0;i < n ; ++i){
    20. dp[0][i] = abs(a[0] - b[i]);
    21. }
    22. for(int i = 1;i < n ; ++i){
    23. int mindp = 0x7f7f7f7f;
    24. for(int j = 0;j < n;++j){
    25. mindp = min(dp[i-1][j],mindp);
    26. dp[i][j] = min(dp[i][j] , mindp + abs(a[i] - b[j]));
    27. }
    28. }
    29. int ans = 0x7f7f7f7f;
    30. for(int i = 0;i < n ; ++i){
    31. ans = min(dp[n - 1][i] ,ans);
    32. }
    33. sort(b,b + n,cmp);
    34. memset(dp,0x7f,sizeof(dp));
    35. for(int i = 0;i < n ; ++i){
    36. dp[0][i] = abs(a[0] - b[i]);
    37. }
    38. for(int i = 1;i < n ; ++i){
    39. int mindp = 0x7f7f7f7f;
    40. for(int j = 0;j < n;++j){
    41. mindp = min(dp[i-1][j],mindp);
    42. dp[i][j] = min(dp[i][j] , mindp + abs(a[i] - b[j]));
    43. }
    44. }
    45. for(int i = 0;i < n ; ++i){
    46. ans = min(dp[n - 1][i] ,ans);
    47. }
    48. printf("%d\n",ans);
    49. return 0;
    50. }




[2016-03-28][POJ][3666][]Making the Grade]

原文:http://www.cnblogs.com/qhy285571052/p/0f251142b5970f12318ac5ce3612fb50.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!