uva 12589——Learning Vector

叁歲伎倆 2022-08-18 11:31 13阅读 0赞

题意：输入n个向量（x，y），要求选出k个，从（0，0）开始画，使得画出来的折线与x轴围成的面积最大。输出面积的二倍。

思路：01背包，dp\[i\]\[j\]表示y的坐标为i且已经选了j个点的最大面积，然后10包选当前点和不选当前点的最大值。

code：

#include <bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    
    const int INF=0x3fffffff;
    const int inf=-INF;
    const int N=1000000;
    const int M=55;
    const int mod=1000000007;
    const double pi=acos(-1.0);
    
    #define cls(x,c) memset(x,c,sizeof(x))
    #define cpy(x,a) memcpy(x,a,sizeof(a))
    #define ft(i,s,n) for (int i=s;i<=n;i++)
    #define frt(i,s,t) for (int i=s;i>=t;i--)
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define lrt  rt<<1
    #define rrt  rt<<1|1
    #define middle int m=(r+l)>>1
    #define lowbit(x) (x&-x)
    #define pii pair<int,int>
    #define mk make_pair
    #define IN freopen("in.txt","r",stdin);
    #define OUT freopen("out.txt","w",stdout);
    
    struct node
    {
        int x,y;
        bool operator <(const node& b)const{
             return b.x*y>b.y*x;
        }
    }g[M];
    int T,n,k;
    int dp[M*M][M];
    int main()
    {
        scanf("%d",&T);
        ft(ca,1,T){
            scanf("%d %d",&n,&k);
            ft(i,0,n-1) scanf("%d %d",&g[i].x,&g[i].y);
            sort(g,g+n);cls(dp,-0x3f);dp[0][0]=0;
            ft(i,0,n-1) frt(j,M*M-1,0) frt(q,k-1,0){
                if (dp[j][q]>=0)
            dp[j+g[i].y][q+1]=max(dp[j+g[i].y][q+1],dp[j][q]+(g[i].y+2*j)*g[i].x);
            }
            int ans=0;
            ft(i,0,M*M-1) ans=max(ans,dp[i][k]);
            printf("Case %d: %d\n",ca,ans);
        }
    }