题意：把n划分成k个数，求最大价值，每个数的价值 由Fi和该数的第i位上是否为3的倍数决定。 给定k<1e6,Fi i<6。Q次询问n
思路；按位考虑的k个数的贡献，那么可以将第i位看成容量为3k的背包，就是一个多重背包，可以用二进制优化，但是这样直接分有问题。因为只能在3的倍数之间转移。又因为在每一位上最多有一个数不是3的倍数。所以我们可以先求出把n划分成k-1个数的最大价值，然后在通过枚举剩下的数更新dp数组。这里显然不能暴力n^2枚举。所以考虑枚举新增的那个数每一位来更新答案
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e6 + 6; ll dp[maxn],f[7],pw[7]; int k,q,n; int main() { scanf("%d",&k);k=3*(k-1); for(int i=0;i<6;i++) scanf("%lld",&f[i]); pw[0]=1; for(int i=1;i<6;i++) pw[i]=pw[i-1]*10; for(int i=0;i<=999999;i++) { ll x=i; for(int j=0;j<6;j++) { if(x%10%3==0) dp[i]+=x%10/3*f[j]; x/=10; } } for(int x=0;x<6;x++) { for(int i=1,j=k;j>0;i*=2) { if(i>j) i=j; for(int j=999999;j>=pw[x]*i*3;j--) { dp[j]=max(dp[j],dp[j-pw[x]*i*3]+i*f[x]); } j-=i; } } scanf("%d",&q); for(int i=1;i<=q;i++) { scanf("%d",&n); printf("%lld\n",dp[n]); } return 0; }