茶叶企业网站开发源码,家政网站建设方案分析,wordpress类似qq空间,网站风格包括什么意思正题
题目链接:https://ac.nowcoder.com/acm/contest/20110/C 题目大意
一个长度为nnn的字符串SSS#xff0c;SSS中存在一些???#xff0c;有N/O/I/PN/O/I/PN/O/I/P四个字符作为字符集#xff0c;每对相邻的字符会产生不同的贡献#xff0c;现在要求所有权值不小于xxx…正题
题目链接:https://ac.nowcoder.com/acm/contest/20110/C 题目大意
一个长度为nnn的字符串SSSSSS中存在一些???有N/O/I/PN/O/I/PN/O/I/P四个字符作为字符集每对相邻的字符会产生不同的贡献现在要求所有权值不小于xxx的字符串中字典序第kkk大的。
1≤n,k≤1000,1≤x≤1091\leq n,k\leq 1000,1\leq x\leq 10^91≤n,k≤1000,1≤x≤109 解题思路
考虑到暴力dfsdfsdfs搜索的瓶颈在于我们可能会搜到大量权值小于xxx的序列所以如果保证我们每次都能搜到满足条件的字符我们就可以O(nk)O(nk)O(nk)解决这个问题。
可以设fi,jf_{i,j}fi,j表示iii个字符是jjj开始往后最多能得到多少权值。
然后根据dpdpdp数组暴力dfsdfsdfs就好了。
时间复杂度O(nk)O(nk)O(nk) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1100;
ll n,l,k,w[4][4],f[N][4],a[N],c[N];
char s[N];
void dfs(ll x,ll p,ll sum){if((c[x]!-1c[x]!p)||sumf[x][p]l||!k)return;a[x]p;if(xnsuml){k--;if(!k){for(ll i1;in;i){if(a[i]0)putchar(N);if(a[i]1)putchar(O);if(a[i]2)putchar(I);if(a[i]3)putchar(P);}putchar(\n);}return;}dfs(x1,3,sumw[p][3]);dfs(x1,1,sumw[p][1]);dfs(x1,0,sumw[p][0]);dfs(x1,2,sumw[p][2]);return;
}
signed main()
{scanf(%lld%lld%lld,n,l,k);scanf(%s,s1);for(ll i1;in;i){if(s[i]N)c[i]0;if(s[i]O)c[i]1;if(s[i]I)c[i]2;if(s[i]P)c[i]3;if(s[i]?)c[i]-1;}for(ll i0;i4;i)for(ll j0;j4;j)scanf(%lld,w[i][j]);memset(f,0xcf,sizeof(f));for(ll i0;i4;i)if(c[n]-1||c[n]i)f[n][i]0;for(ll in-1;i1;i--)for(ll j0;j4;j){if(!(c[i]-1||c[i]j))continue;for(ll k0;k4;k)f[i][j]max(f[i][j],f[i1][k]w[j][k]);}dfs(1,3,0);dfs(1,1,0);dfs(1,0,0);dfs(1,2,0);if(k)puts(-1);return 0;
}
