choose 那里是要用 DP 的,你这时间复杂度有点问题
by SteveFang @ 2020-08-25 02:33:51
建议重学时间复杂度,这个肯定过不了的
by Ryo_Yamada @ 2020-08-25 06:52:26
```cpp
#include<bits/stdc++.h>
using namespace std;
int g[1005];
int main(){
int g1,g2,g3,g5,g10,g20,sum=0;
cin>>g1>>g2>>g3>>g5>>g10>>g20;
for(int i=0;i<=g1;i++){
for(int j=0;j<=g2;j++){
for(int k=0;k<=g3;k++){
for(int l=0;l<=g5;l++){
for(int m=0;m<=g10;m++){
for(int n=0;n<=g20;n++){
g[i+j*2+k*3+l*5+m*10+n*20]=1;
}
}
}
}
}
}
for(int i=1;i<=1005;i++){
if(g[i]==1){
sum++;
}
}
cout<<"Total="<<sum<<endl;
return 0;
}//ac
by 初音のミク @ 2020-08-25 07:29:39
@[胡萝卜兔](/user/254321)
by 初音のミク @ 2020-08-25 07:30:35
@[初音のミク](/user/342604) 您在发什么啊……
by Ryo_Yamada @ 2020-08-25 07:38:35
AC题解(从oj复制过来的)
by 初音のミク @ 2020-08-25 07:40:53
@[初音のミク](/user/342604) 题都不看的吗,这明显不是一道题啊
by Ryo_Yamada @ 2020-08-25 07:41:50
反正我是暴力枚举需要用到的数,用另一个数组标记,然后DP求最大值
最大的点78ms。
我自己的代码:
```cpp
#include <bits/stdc++.h>
using namespace std;
int n,m,a[25],b[25],ans;//b数组用来标记
int dp()//DP过程
{
int f[2005],maxa = 0,ans = 0,t = 0;
memset(f,0,sizeof(f));
f[0] = 1;
for (int i = 1; i <= n; i++)
{
if (b[i] == 0)//能用就继续
{
t = 0;
for (int j = maxa; j >= 0; j--)
{
if (f[j] == 1 && f[j + a[i]] == 0) f[j + a[i]] = 1,ans++,t = max(t,j + a[i]);
}
maxa = max(maxa,t);
}
}
return ans;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
if (m == 0) cout << dp();//开始暴力枚举了。
else if (m == 1)
{
for (int i = 1; i <= n; i++)
{
b[i] = 1;
ans = max(ans,dp());
b[i] = 0;
}
cout << ans;
}
else if (m == 2)
{
for (int i = 1; i <= n; i++)
{
for (int j = i + 1; j <= n; j++)
{
b[i] = 1,b[j] = 1;
ans = max(ans,dp());
b[i] = 0,b[j] = 0;
}
}
cout << ans;
}
else if (m == 3)
{
for (int i = 1; i <= n; i++)
{
for (int j = i + 1; j <= n; j++)
{
for (int k = j + 1; k <= n; k++)
{
b[i] = 1,b[j] = 1,b[k] = 1;
ans = max(ans,dp());
b[i] = 0,b[j] = 0,b[k] = 0;
}
}
}
cout << ans;
}
else if (m == 4)
{
for (int i = 1; i <= n; i++)
{
for (int j = i + 1; j <= n; j++)
{
for (int k = j + 1; k <= n; k++)
{
for (int z = k + 1; z <= n; z++)
{
b[i] = 1,b[j] = 1,b[k] = 1,b[z] = 1;
ans = max(ans,dp());
b[i] = 0,b[j] = 0,b[k] = 0,b[z] = 0;
}
}
}
}
cout << ans;
}
return 0;
}
```
by Level_Down @ 2020-08-25 08:54:51
@[胡萝卜兔](/user/254321)
by Level_Down @ 2020-08-25 08:55:46
总之把 choose 里的换成 DP 就对了
by Level_Down @ 2020-08-25 09:02:56