用来记录一下自己对这道题的理解,先用java编写,代码逻辑是互通的。
题目链接:https://www.luogu.com.cn/problem/P1311
题解链接:https://www.luogu.com.cn/problem/solution/P1311(题解码字有误,建议配合代码阅读)
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n,k,p,t,ans,price;
ans = 0;
t = 0;
// n个客栈 k个色调 有p块钱
n = scanner.nextInt(); //客栈
k = scanner.nextInt(); //色调
p = scanner.nextInt(); //最低消费
int[] num = new int[k+1]; //用来记录颜色对应客栈有多少个
int[] color = new int[n+1]; //用来记录每个客栈的颜色属性
System.out.println("------------------------------");
for(int i=1;i<=n;i++)
{
color[i] = scanner.nextInt();
price = scanner.nextInt();
if(price <= p)
{
//当碰到符合最低消费时,开始记录前面的客栈数到num数组中
for(int j = i; j > t; j--)
num[color[j]]++; //开始记录前面的客栈数
t = i; //更新最后一个符合最低消费的位置
ans += num[color[i]]-1; //减去本身
}
else
ans += num[color[i]];
System.out.println(Arrays.toString(num) + " | " + Arrays.toString(color) + " | " + ans);
}
System.out.printf("%d",ans);
}
ans就是总方案数结果,其实核心就是下面这两句来统计选择方案,按照第二个客栈来选择第一个客栈。
ans+=num[color[i]]-1;
ans+=num[color[i]];
===因为只需要两个客栈之间有最低消费就可以,所以每个第二个客栈可选择的客栈都是前面所有相同色调的客栈===
选择的前提
①有出现最低消费客栈,只有当出现了最低消费的客栈num数组才会开始记录各个色调的客栈数
②第二个客栈与第一个客栈色调相同
③如果第二个客栈是最低消费客栈,要减去本身
有疑问加站长微信联系(非本文作者)