題目描述:
東東開車出去泡妞(在夢中),車内提供了 n 張CD唱片,已知東東開車的時間是 n 分鐘,他該如何去選擇唱片去消磨這無聊的時間呢
假設:
- CD數量不超過20張
- 沒有一張CD唱片超過N分鐘
- 每張唱片隻能聽一次
- 唱片的播放長度為整數
- N也是整數
我們需要找到最能消磨時間的唱片數量,并按使用順序輸出答案(必須是聽完唱片,不能有唱片沒聽完卻到了下車時間的情況發生)
本題是 Special Judge
input:
多組輸入
每行輸入第一個數字N, 代表總時間,第二個數字 M 代表有 M 張唱片,後面緊跟 M 個數字,代表每張唱片的時長 例如樣例一: N=5, M=3, 第一張唱片為 1 分鐘, 第二張唱片 3 分鐘, 第三張 4 分鐘
所有資料均滿足以下條件:
N≤10000
M≤20
output:
輸出所有唱片的時長和總時長,具體輸出格式見樣例
思路:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[10010],v[10010],f[10010];
bool pre[10010][10010];
int main()
{
int m,n;
while(scanf("%d",&m)!=EOF)
{
memset(f,0,sizeof(f));
memset(pre,0,sizeof(pre));
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
for(int j=m;j>=0;j--)
if(j-a[i]>=0)
if(f[j]<=f[j-a[i]]+a[i])
{
f[j]=f[j-a[i]]+a[i];
pre[i][j]=1;
}
int i=n,j=m,sum=0;
while(i>=1&&j>=0)
{
if(pre[i][j])
{
j=j-a[i];
v[++sum]=a[i];
}
i--;
}
for(int i=sum;i>=1;i--)
cout<<v[i]<<" ";
cout<<"sum:"<<f[m]<<endl;
}
return 0;
}