[cf706C]Hard Problem

706C - Hard problem

题意

题意很简单,就是给定$n$串字符串,对每一串字符串只有一种操作,翻转。之后每翻转一个字符串需要消耗$c_i$的能量,问至少需要多少能量是的,这$n$个字符串是以字典序排列的。

ps:相等也算按字典序

题解

dp,定义一个二维数组$dp[i][j]$。其中$i$表示第$i$个字符串中选择$j$产生字典序的最少能量消耗。$j$只有1和0,表示翻转或者不翻转,之后就是四种情况下去。具体可以看代码.

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head

ll n,m,q;
ll d;
const int maxn = 210;
ll num[maxn];
ll dp[maxn][12][22];
ll a[maxn];
ll MOD(ll x,ll mod){
ll tx = x % mod;
if(tx<0) tx += mod;
return tx;
}
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
int T; scanf("%d",&T);
rep(test_case,1,T+1){
scanf("%lld%lld",&n,&q);
rep(i,1,n+1) scanf("%lld",num+i);
printf("Case %d:\n",test_case);
while(q--){
scanf("%lld%lld",&d,&m);
rep(i,1,n+1) a[i] = MOD(num[i],d);
memset(dp,0,sizeof(dp));
rep(i,0,n) dp[i][0][0] = 1;
rep(i,1,n+1){
rep(j,1,m+1){
rep(k,0,d) dp[i][j][k] = dp[i-1][j][k];
rep(k,0,d){
dp[i][j][(k+a[i])%d] += dp[i-1][j-1][k];
}
}
}
printf("%lld\n",dp[n][m][0]);
}
}
return 0;
}