暴力
我一开始做这道题先想到的就是暴力。。。
所以先说一下暴力的做法。首先在输入的时候讲花费小于P的位置标记下来，然后用两层循环枚举所有的两个客栈的组合方案。再用一层循环将两个客栈之间的位置扫一遍，如果有被标记过得位置证明这种方案是可行的。将其统计下来。
暴力的代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstring>
const int maxn = 2e5+
3;
const int maxk =
53;
using namespace std;
int x, f;
char c;
inline int read() {
x =
0, f =
1;
c =
getchar();
while (c <
'0' || c >
'9') {
if(c ==
'-') f = -
1;
c =
getchar();
}
while (c <=
'9' && c >=
'0') {
x = x*
10 + c-
'0';
c =
getchar();
}
return x *
f;
}
int n, k, p, col[maxn], cost[maxn], Ans;
bool book[
1003][
1003];
int main() {
n = read(), k = read(), p =
read();
for(
int i=
1; i<=n; i++
) {
col[i] =
read();
cost[i] =
read();
}
for(
int i=
1; i<=n; i++
) {
for(
int j=i+
1; j<=n; j++
) {
for(
int k=i; k<=j; k++
) {
if(cost[k] <=
p) {
book[i][j] =
true;
}
}
}
}
for(
int i=
1; i<=n; i++
) {
for(
int j=i+
1; j<=n; j++
) {
if(book[i][j] ==
true && col[i] ==
col[j]) {
Ans++
;
}
}
}
printf("%d", Ans);
}
暴力
正解
我们边输入边做处理，考虑用一个cnt[i]表示颜色为i的客栈在当前位置之前有多少个同样颜色的客栈。用一个now表示最后一家花费小于等于P的咖啡店的位置。再用一个last[i]表示最后一家颜色为i的客栈的位置。显然，如果last[i]小于等于now，那就说明当前位置上的客栈可以和之前的所有颜色为i的客栈组合，否则就继续往后扫。重复这些操作，沿途统计有多少种组合
正解的代码
#include <cstdio>
const int maxk =
53;
using namespace std;
int x, f;
char c;
inline int read() {
x =
0, f =
1;
c =
getchar();
while (c <
'0' || c >
'9') {
if(c ==
'-') f = -
1;
c =
getchar();
}
while (c <=
'9' && c >=
'0') {
x = x*
10 + c-
'0';
c =
getchar();
}
return x *
f;
}
int n, k, p, now, color, cost, Ans, cnt[maxk], sum[maxk], last[maxk];
int main() {
n = read(), k = read(), p =
read();
for(
int i=
1; i<=n; i++
) {
color =
read();
cost =
read();
if(cost <=
p)
now =
i;
if(now >=
last[color])
sum[color] =
cnt[color];
Ans +=
sum[color];
last[color] =
i;
cnt[color]++
;
}
printf("%d", Ans);
}
转载于:https://www.cnblogs.com/bljfy/p/9313973.html
相关资源：锣鼓声声迎新春——新年工作计划ppt模板.zip
