win7电脑做网站,公司名称免费起名,上海中国国际进口博览会,亚马逊做国际外贸在哪个网站首先考虑一下给一个数如何求它需要多少次操作。 显然用一个单调栈就可以完成#xff1a;塞入栈中#xff0c;将比它大的所有数都弹出#xff0c;如果栈中没有当前数#xff0c;答案1。 因为数的范围只有0~9#xff0c;所以我们可以用一个二进制数来模拟这个栈#xff0c;… 首先考虑一下给一个数如何求它需要多少次操作。 显然用一个单调栈就可以完成塞入栈中将比它大的所有数都弹出如果栈中没有当前数答案1。 因为数的范围只有0~9所以我们可以用一个二进制数来模拟这个栈并塞到DP的状态里。 设$dp[i][j][k]$表示前i位数已经进行了j次操作栈的状态为k的方案数。 每次枚举一个数的时候先把比这个数大的数在状态中都清零再看看状态中有没有这个数没有的话答案1。 注意需要把状态初始值设为0在栈中...T T #includeiostream
#includecstring
#includecstdlib
#includecstdio
#define ll long long
using namespace std;
ll l, r, K;
ll dp[20][20][110];
int a[20];
ll dfs(int pos, int k, int st, bool limit)
{if(!pos) return kK;if(!limit dp[pos][k][st]!-1) return dp[pos][k][st];int uplimit?a[pos]:9; ll ans0;for(int i0;iup;i){int nowst;for(int ji1;j9;j) now^((now (1j))!0)j;if(st(1i)) ansdfs(pos-1, k, now, limit iup);else if(kK) ansdfs(pos-1, k1, now|(1i), limit iup);}if(!limit) dp[pos][k][st]ans;return ans;
}
ll solve(ll x)
{int pos0;while(x) a[pos]x%10, x/10;return dfs(pos, 0, 1, 1);
}
int main()
{memset(dp, -1, sizeof(dp));scanf(%lld%lld%lld, l, r, K);printf(%lld\n, solve(r)-solve(l-1));
} View Code 转载于:https://www.cnblogs.com/Sakits/p/8034800.html
