题意大概是说给你D个数(1<=ai<=9)求全排列组成的D位数模k(1<=K<=200)最大的那个最大的序列.
一开始想的是把全排列分成两段,bitset维护选的数,最后合并一下找最大的...无奈算错了时间复杂度,其实是16!/8!这个思路的优化意义不大.....
------------------------
看了AC的代码,这个题的状态确实是没有get到的.设一个f[i][j],表示的是余数为i时,对数的使用情况为j(二进制下表示哪些数被使用的状态)时的最大排列
转移的话,是选择某一个数后,对应j状态,%k的余数的排列更新成更大的.
和上一次做到的求符合条件的排列的种数有些类似.
这个用二进制枚举所有状态上一次我还是在费解的开关里看到的..
代码
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<iostream>
#include<cstring>
#include<cctype>
#include<cstdio>
using namespace std;
int d,k,a[20];
long long f[205][1<<16];
inline void qin(int &x)
{
char c=0;x=0;
while(!isdigit(c))c=getchar();
while(isdigit(c))x=x*10+c-'0',c=getchar();
}
signed main()
{
qin(d),qin(k);
for(int i=0;i<d;i++)
qin(a[i]);
memset(f,-1,sizeof(f));
f[0][0]=0;
for(int i=0;i< 1<<d;i++)
{
for(int j=0;j<k;j++)
{
if(f[j][i]==-1)
continue;
for(int l=0;l<d;l++)
{
if(i>>l&1)continue;
long long sta=i|(1<<l),stb=(j*10+a[l])%k;
f[stb][sta]=(f[stb][sta]>f[j][i]*10+a[l]?f[stb][sta]:f[j][i]*10+a[l]);
}
}
}
for(int i=k-1;i>=0;i--)
{
if(f[i][(1<<d)-1]!=-1)
{
printf("%lld",f[i][(1<<d)-1]);
break;
}
}
return 0;
}补题的时候才离谱
记得开O2,用三目运算手写max,记得用手写的快读.....
标签：GCC,排列,long,.....,Largest,include,Remainder,DP From： https://www.cnblogs.com/qbning/p/16637449.html