這個題據(jù)說是水題，有很多種算法
算法1 （樸素）：
1、順序檢索每一個客棧。
2、對于顏色為k的客棧i，搜索在此之前后顏色同為k的客棧j。
3、搜索到以后查找區(qū)間[i,j]內(nèi)消費(fèi)要求小于等于p的客棧，搜索到則總結(jié)果數(shù)sum+1。
1
#include<iostream>
2using namespace std ;
3int main()
4
{
5
long n, k, p ;
6 long color[200000], cost[200000] ;
7 //freopen( "2.in", "r", stdin ) ; freopen( "2.out", "w", stdout ) ;
8 cin >>n >>k >> p ;
9 for ( long i = 0; i < n; i++ ) cin >>color[i] >>cost[i] ;
10 long ans = 0 ;
11 for ( long i = 0; i < n-1; i++ )
12 for ( long j = i+1; j < n ; j++ )
13 if ( color[i]== color[j] )
14
{
15 long temp = 0 ;
16 for ( long cafe = i; cafe <= j && temp == 0 ; cafe++ )
17 if ( cost[cafe] <= p ) temp = 1 ;
18 ans += temp ;
19
}
20 cout << ans ;
21 return 0 ;
22
}
預(yù)期得分40~60
算法二：
當(dāng)然是DP
動態(tài)規(guī)劃，設(shè)f[i,j]為前i個客棧中色調(diào)為j的可行方案，s[i,j]為前i個客棧中可以與之后色調(diào)為j的客棧搭配的客棧數(shù)，即有s[i,j]個客棧的色調(diào)為j，且該客棧與第i個客棧之間有符合條件的咖啡店，v[i]為第i個客棧的最低消費(fèi)，c[i]為第i個客棧的色調(diào)a[i,j]為前i個客棧中色調(diào)為j的客棧的數(shù)目，則有
s[i,j] = ( v[i] <= p ) ? a[i,j] : s[i-1,j]
f[j] = ( c != j ) ? f[j] : f[j]+s[j]
代碼：
1#include <cstdio>
2using namespace std ;
3int main()
4{
5 freopen( "2.in", "r", stdin ) ;
6 freopen( "2.out", "w", stdout ) ;
7 long n, m, p, i, j, ans, v = 0, c = 0 ;
8 long a[50] = {0}, s[50] = {0}, f[50] = {0} ;
9 scanf( "%ld%ld%ld", &n, &m, &p ) ;
10 for ( i = 1; i <=n; i++ )
11 {
12 scanf( "%ld%ld", &c, &v ) ;
13 if ( v <= p )
14 for ( j = 0; j < m; j++ ) s[j] = a[j] ;
15 for ( j = 0; j < m; j++ )
16 f[j] = ( c != j ) ? f[j] : f[j]+s[j] ;
17 a[c]++ ;
18 if ( v <= p ) s[c]++ ;
19 }
20 ans = 0 ;
21 for ( j = 0; j < m; j++ ) ans+= f[j] ;
22 printf( "%ld", ans ) ;
23 return 0 ;
24}