第二场对抗赛，感觉自己和队友已经尽力了，然而时间还是不够，一道简单题调了好久浪费了一些时间
题意： 有一排鸽子，每个鸽子有一个鸽值，只有当一段区间的鸽子的 鸽值的或 大于 这段区间的最大鸽值 时，这段区间的鸽子才愿意出动，现在有q次询问，每次给出一只鸽子，问要使这只鸽子出动，需要至少同时出动多少只鸽子？
算法：ST表、线段树
思路：暴力即可，用ST表或线段树预处理一下，然后从小到大枚举区间，如果碰到满足题意的区间就输出区间大小就行了
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
|
int n,m,a[maxn],ST[maxn][23],STT[maxn][23];
inline void init_st(){
for(int i=1;i<=n;i++) ST[i][0]=STT[i][0]=a[i];
for(int j=1;(1<<j)<=n;j++){
for(int i=1;i+(1<<(j-1))-1<=n;i++){
ST[i][j]=max(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);
STT[i][j]=STT[i][j-1]|STT[i+(1<<(j-1))][j-1];
}
}
}
inline int query(int l,int r,int tp){
int len=log2(r-l+1);
return (tp==1)?max(ST[l][len],ST[r-(1<<len)+1][len]):(STT[l][len]|STT[r-(1<<len)+1][len]);
}
inline int ask(int x){
for(int len=1;len<=n;len++){
for(int i=max(1,x-len+1),j=i+len-1;i<=x;i++,j=i+len-1){
int q1=query(i,j,1);
int q2=query(i,j,2);
if(q2>q1) return len;
}
}
return -1;
}
int main(){
read(n),read(m);
rep(i,1,n) read(a[i]);
init_st();
rep(i,1,m){
int x;
read(x);
printf("%d\n",ask(x));
}
return 0;
}
|
题意： 有$N$个店铺，每个店铺都卖$M$个铳，在第$i$个店铺买$j$个铳需要花$p[i][j]$元，此外，在每家店买大于等于$Y$把铳可以免邮费，否则每把铳需要花费额外$a[i]$的邮费，每家店只能购买一次，问买$K$把铳的最小花费
算法： 分组背包
思路：分组背包裸题。。。就加了一个邮费处理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| int n,m,k,y,a[805],p[805][805],dp[805][805];
int main(){
read(n),read(m),read(k),read(y);
rep(i,1,n) read(a[i]);
rep(i,1,n) rep(j,1,m) read(p[i][j]);
memset(dp,0x3f,sizeof(dp));
dp[0][0]=0;
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++){
for(int l=0;l<=min(j,m);l++){
if(l>=y) dp[i][j]=min(dp[i][j],dp[i-1][j-l]+p[i][l]);
else dp[i][j]=min(dp[i][j],dp[i-1][j-l]+p[i][l]+l*a[i]);
}
}
}
printf("%d\n",dp[n][k]);
return 0;
}
|