题意: 有 n 个团队和 m 艘船，每艘船的载客量为 k，每个团队的人数为ai+1 ，转载该团队可获利润 bi,要求每个团队的所有人必须在同一艘船上，
且团队优先级高的团队所在船编号不能大于优先级低的团队，求可以获得的最大利润。
分析：dp[i] 表示获得 i 利润时需要的最少船位，且要保证优先级高的团队优先考虑。
#include <stdio.h> #include <string.h> #define INF 0x1f1f1f1f #define v 10005 int min(int a,int b) { return a<b?a:b; } int dp[v+1]; int n,m,k; int cal(int num,int a) { int tot=(num+k-1)/k; if(num + a<= tot*k) return num+a; return tot*k+a; } int main() { int t,i; scanf("%d",&t); while(t--) { scanf("%d %d %d",&n, &m, &k); memset(dp,INF,sizeof(dp)); int a,b; dp[0]=0; while(n--) { scanf("%d %d",&a, &b); a++; for(i=v-1; i>=b; i--) if(dp[i-b]!=INF) dp[i]=min(dp[i],cal(dp[i-b],a)); } for( i=v; i>=0; i--) if(dp[i]<m*k) break; printf("%d\n",i); } return 0; }