UVA - 12589 Learning Vector（01背包）

题目链接

---

贪心部分

决策是混乱的，如何求得最后的最大面积呢？这就用到计算几何的一些知识了，要想总的面积越大，也就是前面的向量越上凸越好，因此我们需要将所有向量先贪心地按照高度降序处理，接着开始DP

DP部分

考虑到每个点选或不选，而且可以从前向后转移，那么设$d[i][j][k]$，代表考虑当前第$i$个点，已经选过了$j$个点，当前高度为$k$，那么有：

$d[i][j][k]=max(d[i][j][k],d[i-1][j-1][k-p[i].y]+f(p[i],k-p[i].y))$

注意本题的边界是负无穷而不是0，因为这个高度是在前面的向量必须选过之后才能累加的，如果初始化为0，就从原本不存在的高度累积答案，这是错误的！

最终答案是$d[n][m][i],0\le i\le H$

易错点

如果写未使用滚动数组优化的DP，那么一下代码是错误的：

memset(d,0x8f,sizeof d); d[0][0][0]=0; for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) for(int k=0;k<=H;k++){ d[i][j][k]=d[i-1][j][k]; if(k-p[i].y>=0) d[i][j][k]=max(d[i][j][k],d[i-1][j-1][k-p[i].y]+f(p[i],k-p[i].y)); }

这个错误还不容易看出，因为我们写的是$j=0$（注意这里不能从1开始，前面那道守卫仓库就是这样的错误），而$d[i][j][k]=max(d[i][j][k],d[i-1][j-1][k-p[i].y]+f(p[i],k-p[i].y))$，这里有$j-1$，那么明显发生了数组下标为$-1$的情况，这样的话整个过程的数据都乱了，因此要这样判断：

$if(k-p[i].y>=0\&\&j>=1)d[i][j][k]=max(d[i][j][k],d[i-1][j-1][k-p[i].y]+f(p[i],k-p[i].y))$

当然写滚动数组是不容易出现这种错误的，以后要多写滚动数组

#include <set> #include <map> #include <stack> #include <queue> #include <math.h> #include <cstdio> #include <string> #include <bitset> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <unordered_map> using namespace std; #define fi first #define se second #define pb push_back #define ins insert #define lowbit(x) (x&(-x)) #define mkp(x,y) make_pair(x,y) #define mem(a,x) memset(a,x,sizeof a); typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair<int,int> P; const double eps=1e-8; const double pi=acos(-1.0); const int inf=0x3f3f3f3f; const ll INF=1e18; const int Mod=1e9+7; const int maxn=2e5+10; struct node{ int x,y; bool operator < (const node &p) const { return y*p.x>x*p.y; } }p[55]; int d[55][55*55]; int f(node t,int h){ return 2*h*t.x+t.x*t.y; } int main(){ //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t,n,m,kase=0; scanf("%d",&t); while(t--){ int H=0; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d%d",&p[i].x,&p[i].y); H+=p[i].y; } sort(p+1,p+1+n); /*d[0][0][0]=0; for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) for(int k=0;k<=H;k++){ d[i][j][k]=d[i-1][j][k]; if(k-p[i].y>=0 && j>=1) d[i][j][k]=max(d[i][j][k],d[i-1][j-1][k-p[i].y]+f(p[i],k-p[i].y)); }*/ memset(d,0x8f,sizeof d); d[0][0]=0; for(int i=1;i<=n;i++) for(int j=m;j>=1;j--) for(int k=H;k>=p[i].y;k--){ d[j][k]=max(d[j][k],d[j-1][k-p[i].y]+f(p[i],k-p[i].y)); } int ans=0; for(int i=0;i<=H;i++) ans=max(ans,d[m][i]); printf("Case %d: %d\n",++kase,ans); } return 0; }