The Highest Mark---hdu5501(问题转化 01背包)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5501

二维数组：

#include<stdio.h>

#include<iostream>

#include<string.h>

#include<algorithm>

#include<queue>

using namespace std;

#define N 3100

int dp[N][N];

struct node

{

    int A, B, C;

}a[N];

int cmp(node p, node q)

{

    return p.C*q.B < p.B*q.C;

}

int main()

{

    int T, n, t;

    scanf("%d", &T);

    while(T--)

    {

        memset(a, , sizeof(a));

        memset(dp, , sizeof(dp));

        scanf("%d%d", &n, &t);

        for(int i=; i<n; i++)

        {

            scanf("%d%d%d", &a[i].A, &a[i].B, &a[i].C);

        }

        sort(a, a+n, cmp);

        int ans = ;

        for(int i=; i<n; i++)

        {

            for(int j=; j<=t; j++)

            {

                if(j<a[i].C)

                    dp[i+][j] = dp[i][j];

                else

                    dp[i+][j] = max(dp[i][j], dp[i][j-a[i].C]+a[i].A-j*a[i].B);

                ans=max(dp[i+][j],ans);

            }

        }

        printf("%d\n", ans);

    }

    return ;

}

一维数组：

#include<stdio.h>

#include<iostream>

#include<string.h>

#include<algorithm>

#include<queue>

using namespace std;

#define N 3100

int dp[N];

struct node

{

    int A, B, C;

}a[N];

int cmp(node p, node q)

{

    return p.C*q.B < p.B*q.C;

}

int main()

{

    int T, n, t;

    scanf("%d", &T);

    while(T--)

    {

        memset(a, , sizeof(a));

        memset(dp, , sizeof(dp));

        scanf("%d%d", &n, &t);

        for(int i=; i<n; i++)

        {

            scanf("%d%d%d", &a[i].A, &a[i].B, &a[i].C);

        }

        sort(a, a+n, cmp);

        int ans = ;

        for(int i=; i<n; i++)

        {

            for(int j=t; j>=a[i].C; j--)

            {

                dp[j] = max(dp[j], dp[j-a[i].C]+a[i].A-j*a[i].B);

                ans = max(ans, dp[j]);

            }

        }

        printf("%d\n", ans);

    }

    return ;

}