首页 > ACM题库 > HDU-杭电 > hdu 2078 复习时间-动态规划-[解题报告]C++
2013
12-29

hdu 2078 复习时间-动态规划-[解题报告]C++

复习时间

问题描述 :

为了能过个好年,xhd开始复习了,于是每天晚上背着书往教室跑。xhd复习有个习惯,在复习完一门课后,他总是挑一门更简单的课进行复习,而他复习这门课的效率为两门课的难度差的平方,而复习第一门课的效率为100和这门课的难度差的平方。xhd这学期选了n门课,但是一晚上他最多只能复习m门课,请问他一晚上复习的最高效率值是多少?

输入:

输入数据的第一行是一个数据T,表示有T组数据。
每组数据的第一行是两个整数n(1 <= n <= 40),m(1 <= m <= n)。
接着有n行,每行有一个正整数a(1 <= a <= 100),表示这门课的难度值。

输出:

输入数据的第一行是一个数据T,表示有T组数据。
每组数据的第一行是两个整数n(1 <= n <= 40),m(1 <= m <= n)。
接着有n行,每行有一个正整数a(1 <= a <= 100),表示这门课的难度值。

样例输入:

2
2 2
52
25
12 5
89
64
6
43
56
72
92
23
20
22
37
31

样例输出:

5625
8836 

题目链接

这题我一看就想到了DP,然后也按着DP做了,然后一次就AC了

但是,我从网上找了下别人的思路,又有种想哭的感觉

别人只是找到最小的算一下平方差,就过了,仔细考虑了一下,也对

两个数的平方差>与中间任意几个数的平方差的和

在此我是不是应该反思一下,我的DP代码是否是真的对了呢

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int main()
{
    int i,cas,n,m,ans;
    int a[45];
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d%d",&n,&m);
        for(i=0;i<n;i++)
        scanf("%d",&a[i]);
        sort(a,a+n);
        ans=(100-a[0])*(100-a[0]);
        printf("%d\n",ans);
    }
    return 0;
}

这个是DP做的

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
bool cmp(const int &a,const int &b)
{
    return a>b?1:0;
}
int main()
{
    int i,j,cas,n,m,ans;
    int dp[45][105],a[45][45],c[45];
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d%d",&n,&m);
        memset(dp,0,sizeof(dp));
        memset(a,0,sizeof(a));
        for(i=1;i<=n;i++)
        scanf("%d",&c[i]);
        sort(c+1,c+n+1,cmp);
        c[0]=100;
        for(i=0;i<=n;i++)
        {
            for(j=0;j<=i;j++)
            {
                a[i][j]=(c[i]-c[j])*(c[i]-c[j]);
            }
        }
    //    printf("%d %d %d\n",a[1][0],a[2][0],a[0][0]);
        ans=0;
        for(i=1;i<=m;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(i==1) dp[i][j]=a[j][0];
                else
                dp[i][j]=max(dp[i][j],dp[i-1][j-1]+a[j][j-1]);
                ans=max(ans,dp[i][j]);
            }
        }
        printf("%d\n",ans);

    }
    return 0;
}

解题转自:http://blog.csdn.net/littlefool5201314/article/details/9978365


  1. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;

  2. 因为是要把从字符串s的start位到当前位在hash中重置,修改提交后能accept,但是不修改居然也能accept

  3. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?