题目
思路&题解
我的思路：
显然这道题是状压dp，但是这个限制条件怎么搞？我dp怎么这么菜啊
正解
首先还是考虑状压，因为注意到n很小，且B也很小，可以设dp[i][S]表示第i天为止，S是一个七进制的状压，第j位表示第j个零食还有多少天可以吃。然后就变成sb状压dp了（其实就是我太菜了），但是这道题需要卡空间，且还要写高精度，直接用滚动数组与__int128即可
代码
#include<cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
#define ll __int128
const int MAXN = 5e5 + 3;
inline char GetChar(){
static char buf[10001],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,10001,stdin),p1==p2)?EOF:*p1++;
}
inline void Read(ll &n){
short f=1;
long long x=0;
char c=GetChar();
while(isdigit(c)==false){
if(c=='-'){
f=-1;
}
c=GetChar();
}
while(isdigit(c)==true){
x=((x<<3)+(x<<1)+(c^48));
c=GetChar();
}
n=x*f;
}
void print(__int128 x){
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar(x%10+'0');
}
int n , m;
ll a[6] , b[6] , c[MAXN] , dp[2][1<<13] ;
int f[5] = { 1 , 7 ,49 , 49*7 }, s[45];
int main(){
scanf( "%d%d" , &n , &m );
for( int i = 1 ; i <= n ; i ++ ) Read( a[i] );
for( int i = 1 ; i <= n ; i ++ ) Read( b[i] );
for( int i = 1 ; i <= m ; i ++ ) Read( c[i] );
for( int i = 0 ; i <= 1 ; i ++ )
for( int j = 0 ; j < ( 1 << 12 ) ; j ++ )
dp[i][j] = -1e19;
dp[0][0] = 0;
for( int i = 0 ; i < m ; i ++ ){
int i1 = i & 1 , i11 = i1 ^ 1;
for( int j = 0 ; j < ( 1 << 12 ) ; j ++ )
dp[i11][j] = -1e19;
for( int j = 0 ; j < ( 1 << 12 ) ; j ++ ){
int j1 = j , p = 0;
if( dp[i1][j] == -1e19 ) continue;
for( int k = 1 ; k <= 5 ; k ++ ) s[k] = 0;
while( j1 > 6 ){
s[++p] = j1 % 7;
j1 /= 7;
}
s[++p] = j1 % 7;
for( int k = 1 ; k <= n ; k ++ ){
if( s[k] == 0 ){
int j2 = 0;
for( int k1 = 1 ; k1 <= n ; k1 ++ ){
if( k1 == k ) j2 += f[k1-1] * b[k1];
else if( s[k1] == 0 ) continue;
else j2 += f[k1-1] * ( s[k1] - 1 );
}
dp[i11][j2] = max( dp[i11][j2] , dp[i1][j] + a[k] * c[i+1] );
//printf( "0\n" );
}
}
}
}
ll ans = -1e19;
for( int j = 0 ; j < ( 1 << 12 ) ; j ++ )
ans = max( ans , dp[m&1][j] );
if( ans == -1e19 )
printf( "Poor W." );
else
print( ans );
return 0;
}
