題意：輸入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);} }

總結

以上是生活随笔為你收集整理的uva 12589——Learning Vector的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。