uva12589 Learning Vector

比赛的时候没想到是背包的dp啊。。。
思路:先按斜率排序,因为对于确定的一些向量,一定是斜率大的在前可以使总面积最大化。dp方程主体是背包,但是加了一维,表示最右侧的向量的最高点的y值。也就是dp[i][j][k]表示前i个向量中选取j个且最右侧高为k的最大面积。可以用滚动数组省掉阶段那一维,然后和一般背包不同的是,因为如果填表的话,每次对于dp[i][j][k],都要枚举dp[i-1][j-1][0……k-1],复杂度很高,所以用刷表的方式,每次用dp[i][j][k]更新dp[i+1][j+1][k+p[i].y]。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
typedef struct Point{
    int x,y;
}Point;
Point p[60];
bool cmp(Point a,Point b)
{
    return a.y*b.x>b.y*a.x;
}
int dp[60][3000];
int main()
{
    int i,j,r,cases=0;
    int t,n,k;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&k);
        memset(dp,-inf,sizeof(dp));dp[0][0]=0;
        for(i=1;i<=n;i++)
            scanf("%d%d",&p[i].x,&p[i].y);
        sort(p+1,p+1+n,cmp);
        for(i=1;i<=n;i++)
        {
            for(j=k;j>=0;j--)
            {
                for(r=0;r<=50*n;r++)
                {
                    if(dp[j][r]==-inf) continue;
                    int tmp=dp[j][r]+(r+p[i].y+r)*p[i].x;
                    if(tmp>dp[j+1][r+p[i].y])
                        dp[j+1][r+p[i].y]=tmp;
                }
            }
        }
        int ans=-inf;
        for(r=0;r<=50*n;r++) if(dp[k][r]>ans) ans=dp[k][r];
        printf("Case %d: %d\n",++cases,ans);

    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>