L3 |
您所在的位置:网站首页 › ull的单词 › L3 |
题目链接 给定一个全部由小写英文字母组成的字符串,允许你至多删掉其中 3 个字符,结果可能有多少种不同的字符串? 输入格式: 输入在一行中给出全部由小写英文字母组成的、长度在区间 [4, 10^6 ] 内的字符串。 输出格式: 在一行中输出至多删掉其中 3 个字符后不同字符串的个数。 输入样例: ababcc输出样例: 提示: 删掉 0 个字符得到 “ababcc”。 删掉 1 个字符得到 “babcc”, “aabcc”, “abbcc”, “abacc” 和 “ababc”。 删掉 2 个字符得到 “abcc”, “bbcc”, “bacc”, “babc”, “aacc”, “aabc”, “abbc”, “abac” 和 “abab”。 删掉 3 个字符得到 “abc”, “bcc”, “acc”, “bbc”, “bac”, “bab”, “aac”, “aab”, “abb” 和 “aba”。 答案: #include #include #define ll long long #define ull unsigned long long #define INF 0x3f3f3f3f #define inf 0x3f3f3f3f3f3f3f3f #define mem(a,b) memset(a,b,sizeof(a)) #define rep(i,a,b) for(auto i=a;i=b;--i) #define lowbit(x) x&(-x) #define PII pair #define PLL pair #define PI acos(-1) #define pb push_back #define eps 1e-8 #define x first #define y second const int mod = 1e9 + 7; const int MOD = 1e4+7; const int N = 1e6 + 10; const int M = 1111; int dx[]={-1, 0, 1, 0}; int dy[]={0, 1, 0, -1}; int dxy[][2]={{0,1},{1,0},{1,1},{-1,1}}; using namespace std; char s[N]; ll dp[N][4]; void solve(){ cin>>(s+1); int len=strlen(s+1); dp[0][0]=1; for(int i=1;i //删除次数最大为3 dp[i][j]=dp[i-1][j]; //这一位不删,加上前i-1位的个数 if(j) dp[i][j]+=dp[i-1][j-1]; for(int k=i-1;k>=1&&(i-k) dp[i][j]-=dp[k-1][j-(i-k)]; break; } } } } ll res=0; for(int j=0;j ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); return 0; } |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |