I - 邱老师选妹子(二)
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Submit Status
邱老师长得帅这是人尽皆知，于是追他的妹子就会很多。但是你知道，邱老师是一个很专一的人，所以他心里面只能有一个人。于是他决定从追他的众多妹子里挑选一个出来。
在第一轮的选拔中，剩余了一些妹子。酱神又给邱老师出主意了，因为最近酱神刚刚学习了最长上升子序列，所以这次，依然是把妹子们编号，从l到r，一共r-l+1个，这次要求妹子的
编号按照字符来处理，使得最长上升子序列正好是k，比如123是3，321是1.
求剩下的妹子的个数
Input
一开始是一个整数t<=1000，表示的是数据组数，接下来t行，每行是l，r，k 0<l<=r<2^63-1 1<=k<=10
Output
每组数据输出占一行，为一个整数，表示剩下的妹子的个数
Sample input and output
| Sample Input | Sample Output |
|---|---|
1 |
139 |
解题思路:
贪心维护最长上升子序列即可
f(i,f1,f2,f3,k)
i -> 正在转移第 i 位
f1 -> 前面是否大于过下界
f2 -> 前面是否小于过上界
f3 -> 是否有前导0
k -> 前面出现的数的集合 (贪心维护最大)
为什么这样是正确的呢？
我们考虑这样的数字 1 4 3
我们认为最长上升显然是 1 3 ，而不会考虑到1 4，这样可以保证不会遗漏解，故是正解的
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
typedef long long ll;
using namespace std; int tark,maxlen;
string A,B;
ll f[][][][][<<]; inline int GetLength(int k)
{
int len = ;
for(int i = ; i < ; ++ i)
if (k >> i & )
len++;
return len;
} inline int tanxinset(int k,int pos) //贪心维护
{
for(int i = pos ; i < ; ++ i)
if (k >> i & )
return (k & ~( << i) ) | ( << pos);
return k | ( << pos);
} ll dp(int cur,int f1,int f2,int f3,int k)
{
if (f[cur][f1][f2][f3][k] != -)
return f[cur][f1][f2][f3][k];
ll &ans = f[cur][f1][f2][f3][k] = ;
if (cur == maxlen)
{
int len = GetLength(k);
if (len == tark)
return ans = ;
else
return ans = ;
}
int st = f1?:A[cur]-'';
int ed = f2?:B[cur]-'';
for(int i = st ; i <= ed ; ++ i)
{
if (f3 && i == ) //拥有前导零,这个不算上升的
ans += dp(cur+, f1 | i > A[cur]-'' , f2 | i < B[cur]-'' , f3 & !i, );
else
ans += dp(cur+, f1 | i > A[cur]-'' , f2 | i < B[cur]-'' , f3 & !i, tanxinset(k,i) );
}
return ans;
} int main(int argc,char *argv[])
{
std::ios::sync_with_stdio(false);
std::cin.tie();
int Case;
cin >> Case;
while(Case--)
{
cin >> A >> B >> tark;
memset(f,-,sizeof(f));
maxlen = B.size();
while(A.size() != maxlen)
A = '' + A;
printf("%lld\n",dp(,,,,));
}
return ;
}