奇怪的银行

题面

某银行因不明原因,突然限制客户取钱,限制客户一次操作只能取下列情况之一的金额:

  • $ 1 $元

  • $ 6 $元, $ 6^{2} $元, $ 6^{3} $元…

  • $ 9 $元, $ 9^{2} $元, $ 9^{3} $元…

至少需要多少次操作才能取出$N$($1\leq N \leq 100000$)元。不允许边存边取。

分析

通过简单的计算,我们不难推出最多取$7$次,就一定能取完。

设$f[i]$为取$i$元钱至少要的操作次数。

那么$f[i]$一定是有上一个再取$1$或$6^{k}$或$9^{k}$元得到的。

转移方程:$f[i]=\begin{cases}min(f[i-sum1]+1,f[i])\min(f[i-sum2]+1,f[i])\min(f[i],f[i-1]+1)\end{cases}$

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(int i=1;i<=n;i++)f[i] = inf;
f[1] = 1;
f[0] = 0;
for(int i=2;i<=n;i++)
{
int sum1 = 6,sum2 = 9;
for(int j=1;j<=7;j++)
{
if(i - sum1 >= 0)f[i] = min(f[i - sum1] + 1,f[i]);
if(i - sum2 >= 0)f[i] = min(f[i - sum2] + 1,f[i]);
f[i] = min(f[i],f[i - 1] + 1);
sum1 *= 6,sum2 *= 9;
}
}

序列涂色

题面

给你一个长度为$N$的序列:$A={A_{1},A_{2},…,A_{N}}$,对于$N$个整数,我们可以为每一个整数涂上颜色。但要求满足下面这个条件:

如果$A_{i}$与$A_{j}(i<j)$被涂上同一种颜色,那一定满足$A_{i}<A_{j}$

找到满足上述条件的最小颜色数。

$1 \leq N \leq 10^5$,$0 \leq A_i \leq 10^9$

分析

这题思路很明确。。。

设$f[i]$为前$i$个数所涂的最小颜色数,$f[i]=min(f[i],f[j]+1)(a[i]<a[j],i<j)$

$10^{5}$的数据你去跑呀。。。

这道题再加个二分即可,如果$f[mid]<a[i]$,那么我们应该往左边找;如果$f[mid] > a[i]$我们就应该往右找。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for(int i=1;i<=n;i++)
{
l = 1,r = cnt,m = 0;
int flag = 0;
while(l <= r)
{
int mid = (l + r) >> 1;
if(f[mid] < a[i])
{
flag = mid;
r = mid - 1,m = 1;
}
else l = mid + 1;
}
if(!m)f[++cnt] = a[i];
else f[flag] = a[i];
}