题目大意：略。
解题思路：DFS --> TLE；难点在于如何把直线问题转换成01背包问题：在相同角度基础上并且到原点距离短的优先在前排序后：
AC-1：先把相等角度的情况下，后者加上前者的 t 和 v，把它看成一个整体的状态来思考，最后通过 mk[i] 来控制跳跃到上一个不相等的元素。
AC-2：将在后面的元素的时间加上相邻前面元素（在一条直线上）的时间，可以理解成离散状态，该点需要的时间是ti+=t(i-1)，但是这里需要另外声明临时变量，不可以用数组来加否则会影响dp结果。
TLE 代码
/
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); using namespace std; typedef long long ll; struct node { double a; int t,v,s; }; node nds[300]; int vis[300]; int n,m,x,y,rs,ans,pre; int cmp(node n1,node n2) { if(n1.a==n2.a) return n1.s<n2.s; return n1.a<n2.a; } void init() { ans=rs=0; mem(vis,0); nds[0].a=0; } void dfs(int k) { if(k>m) { rs=max(rs,ans-pre); return; } for(int i=1;i<=n;i++) { if(vis[i]==0 && (nds[i-1].a==nds[i].a&&vis[i-1]==1 || nds[i-1].a!=nds[i].a)) { vis[i]=1; ans+=nds[i].v; pre=nds[i].v; dfs(k+nds[i].t); ans-=nds[i].v; vis[i]=0; } } } int main() { while(~scanf("%d%d",&n,&m)) { init(); for(int i=1;i<=n;i++) { scanf("%d%d%d%d",&x,&y,&nds[i].t,&nds[i].v); nds[i].a=y*1.0/x; nds[i].s=y*y+x*x; } sort(nds+1,nds+1+n,cmp); dfs(0); printf("%d\n",rs); } return 0; }
AC-1 代码
#include<bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof a) using namespace std; typedef long long ll; struct node { double a; int t,v,s; }; node nds[300]; int n,m,x,y; int dp[300][40000+100]; int cmp(node n1,node n2) { if(n1.a==n2.a) return n1.s<n2.s; return n1.a<n2.a; } int main() { int n,m; while(~scanf("%d%d",&n,&m)) { mem(dp,0); for(int i=1;i<=n;i++) { scanf("%d%d%d%d",&x,&y,&nds[i].t,&nds[i].v); nds[i].a=y*1.0/x; nds[i].s=y*y+x*x; } sort(nds+1,nds+1+n,cmp); int idx=1,mk[300]; mk[1]=1; // 与 nds[i] 同步 for(int i=2;i<=n;i++) if(nds[i].a!=nds[i-1].a) mk[i]=++idx; else mk[i]=idx; for(int i=1;i<=n;i++) { if(nds[i].a==nds[i-1].a) { nds[i].t+=nds[i-1].t, nds[i].v+=nds[i-1].v; for(int j=m;j>=0;j--) { if(j>=nds[i].t) dp[i][j]=max(dp[i-1][j],dp[mk[i]-1][j-nds[i].t]+nds[i].v); // mk[i]-1 可以打印dp看看分析下，因为要跳过前一个相同的，因为已经把前一个的t和v加上去了，表示把多个看为一个整体 else dp[i][j]=dp[i-1][j]; } } else for(int j=m;j>=0;j--) { if(j>=nds[i].t) dp[i][j]=max(dp[i-1][j],dp[i-1][j-nds[i].t]+nds[i].v); else dp[i][j]=dp[i-1][j]; } } // for(int i=0;i<=n;i++) // { // for(int j=0;j<=m;j++) // { // printf("%d ",dp[i][j]); // } // puts(""); // } printf("%d\n",dp[n][m]); } return 0; }
AC-2 代码：
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a) using namespace std; typedef long long ll; struct node { double a; int t,v,s; }; node nds[300]; int n,m,x,y; int dp[40000+100]; int cmp(node n1,node n2) { if(n1.a==n2.a) return n1.s<n2.s; return n1.a<n2.a; } int main() { int n,m; while(~scanf("%d%d",&n,&m)) { mem(dp,0); for(int i=0;i<n;i++) { scanf("%d%d%d%d",&x,&y,&nds[i].t,&nds[i].v); nds[i].a=y*1.0/x; nds[i].s=hypot(x,y); // nds[i].s=y*y+x*x; } sort(nds,nds+n,cmp); int t=0; for(int i=0;i<n;i++) { // if(nds[i].a==nds[i-1].a) // 因为会影响到下面计算 j-nds[i].t 的结果，功能上是与下面?:代码一样的 // nds[i].t+=nds[i-1].t; nds[i].a==nds[i-1].a?t+=nds[i].t:t=nds[i].t; for(int j=m;j>=t;j--) dp[j]=max(dp[j],dp[j-nds[i].t]+nds[i].v); } printf("%d\n",dp[m]); } return 0; }
