題意：給定n個數，放到m個容器里，每個容器的容量是t（n個數的累加和不超過t），在不打亂放的順序的情況下問最多能放多少個數？

思路：多維dp，f[i][j[k]表示前i個數放到第j個容器放k個的最大數量。則不放的狀態為f[i-1][j][k],放為f[i-1][j-1][k](放在第一個）f[i-1][j-1][k-v[i]]+1(不是放在第一個）。

code:

#include <bits/stdc++.h> using namespace std;const int N=1005; int v[N],f[N][120][120];int main() {int T,n,m,t,x;scanf("%d",&T);while (T--){scanf("%d%d%d",&n,&t,&m);int len=0;for (int i=1;i<=n;i++){if (i==1) scanf("%d",&x);else scanf(",%d",&x);if (x<=t) v[++len]=x;}n=len;memset(f,0,sizeof(f));for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)for (int k=0;k<=t;k++){f[i][j][k]=f[i-1][j][k];if (k>=v[i]){f[i][j][k] = max(f[i][j][k], f[i-1][j][k-v[i]]+1);f[i][j][k] = max(f[i][j][k], f[i-1][j-1][t]+1);}}printf("%d\n",f[n][m][t]);if (T) puts("");}}

總結

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

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