首页 > ACM题库 > HDU-杭电 > hdu 1976 Software Version-动态规划-[解题报告]C++
2013
12-26

hdu 1976 Software Version-动态规划-[解题报告]C++

Software Version

问题描述 :

相信大家一定有过在网上下载软件而碰到多个不同版本的情况。

一般来说,软件的版本号由三个部分组成,主版本号(Major Version Number),子版本号(Minor Version Number)和修订号(Revision_Number)。当软件进行了重大的修改时,主版本号加一;当软件在原有基础上增加部分功能时,主版本号不变,子版本号加一;当软件仅仅修正了部分bug时,主版本号和子版本号都不变,修正号加一。
在我们比较软件的两个版本的新旧时,都是先比较主版本号,当主版本号相同时再比较子版本号,前两者都相同的情况下再比较修正号。版本号越大的软件越新。

现在,Lele 在载软件的时候碰到了两个版本,请你告诉他哪个版本更新一些。

输入:

输入的第一行有一个整数T,代表有T组测试。接下来有T组测试。
每组测试分两行,第一行有三个整数代表第一个软件版本的主版本号,子版本号和修订号。第二行也有三个整数代表第二个软件版本的主版本号,子版本号和修订号。

数据中出现的整数都在[0,1000]范围之内。

输出:

输入的第一行有一个整数T,代表有T组测试。接下来有T组测试。
每组测试分两行,第一行有三个整数代表第一个软件版本的主版本号,子版本号和修订号。第二行也有三个整数代表第二个软件版本的主版本号,子版本号和修订号。

数据中出现的整数都在[0,1000]范围之内。

样例输入:

3
1 1 0
1 1 1
1 1 1
1 1 0
1 1 1
1 1 1

样例输出:

Second
First
Same

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int dp[50005][3],val[50005],a[50005];

int main()
{
    int t,k,n,m,l;
    scanf("%d",&t);
    while(t--)
    {
        int t;
        scanf("%d",&n);
        int i,j;
        for(i = 1; i<=n; i++)
            scanf("%d",&a[i]);
        scanf("%d",&k);
        l = 1;
        memset(val,0,sizeof(val));
        for(i = 1; i<=n-k+1; i++)
        {
            for(j = i; j<i+k; j++)
            {
                val[i]+=a[j];
            }
        }
        l = n-k+1;
        memset(dp,0,sizeof(dp));
        dp[0][0] = val[1];
        for(i = 1; i<=l; i++)
        {
            dp[i][0] = max(dp[i-1][0],val[i]);
        }
        for(i = k+1; i<=l; i++)
        {
            dp[i][1] = max(dp[i-1][1],dp[i-k][0]+val[i]);
        }
        for(i = 2*k+1; i<=l; i++)
            dp[i][2] = max(dp[i-1][2],dp[i-k][1]+val[i]);
        printf("%d\n",dp[l][2]);

    }

    return 0;
}

解题转自:http://blog.csdn.net/libin56842/article/details/9067241


  1. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢