题面
题解
现场得分：100/100
这是一道比较简单的题目
下发题解
我的做法
- 我是从后往前扫的。
- 记(f_{i,j,0/1/2})表示当前从后往前弄到第(i)位，第(i)位及以后的位置为开头的区间已经有(j)个比较大了，当前这一位(T_i)和(S_i)的大小关系（(T_i<S_i)为0，等于为1，大于为2）。
- 转移显然。
代码
题解
# include <bits/stdc++.h>
using namespace std;
namespace Base{
# define mr make_pair
typedef long long ll;
typedef double db;
const int inf = 0x3f3f3f3f, INF = 0x7fffffff;
const ll infll = 0x3f3f3f3f3f3f3f3fll, INFll = 0x7fffffffffffffffll;
template<typename T> void read(T &x){
x = 0; int fh = 1; double num = 1.0; char ch = getchar();
while (!isdigit(ch)){ if (ch == '-') fh = -1; ch = getchar(); }
while (isdigit(ch)){ x = x * 10 + ch - '0'; ch = getchar(); }
if (ch == '.'){
ch = getchar();
while (isdigit(ch)){num /= 10; x = x + num * (ch - '0'); ch = getchar();}
}
x = x * fh;
}
template<typename T> void chmax(T &x, T y){x = x < y ? y : x;}
template<typename T> void chmin(T &x, T y){x = x > y ? y : x;}
}
using namespace Base;
const int N = 2010, P = 1e9 + 7;
int f[N][N], n, m, q[N], g[N][N];
char s[N];
int main(){
freopen("string.in", "r", stdin);
freopen("string.out", "w", stdout);
read(n); read(m);
scanf("
%s", s + 1);
for (int i = 1; i <= n; i++) s[i] = 'z' - s[i];
f[0][0] = 1;
for (int k = 0; k <= m; k++)
for (int i = 1; i <= n; i++){
bool fg = false;
f[k][i] = (f[k][i] + (f[k][i - 1] + g[k][i - 1]) * (26ll - s[i] - 1)) % P;
g[k][i] = (1ll * g[k][i] + f[k][i - 1] + g[k][i - 1]) % P;
for (int j = i; j <= n; j++){
int ex = (j - i + 1) * (n - j + 1);
if (ex + k > m){
fg = true;
break;
}
f[k + ex][j] = (f[k + ex][j] + 1ll * f[k][i - 1] * s[j]) % P;
}
if (fg == true){
for (int j = n; j >= i; j--){
int ex = (j - i + 1) * (n - j + 1);
if (ex + k > m){
fg = true;
break;
}
f[k + ex][j] = (f[k + ex][j] + 1ll * f[k][i - 1] * s[j]) % P;
}
}
}
printf("%d
", (f[m][n] + g[m][n]) % P);
return 0;
}
我的
#include<bits/stdc++.h>
#define LL long long
#define MOD 1000000007
#define MAXN 2010
using namespace std;
template<typename T>void Read(T &cn)
{
char c; int sig = 1;
while(!isdigit(c = getchar())) if(c == '-') sig = -1; cn = c-48;
while(isdigit(c = getchar())) cn = cn*10+c-48; cn*=sig;
}
template<typename T>void Write(T cn)
{
if(cn < 0) {putchar('-'); cn = 0-cn; }
int wei = 0; T cm = 0; int cx = cn%10; cn/=10;
while(cn) wei++, cm = cm*10+cn%10, cn/=10;
while(wei--) putchar(cm%10+48), cm /= 10;
putchar(cx+48);
}
template<typename T>void Max(T &cn, T cm) {cn = cn < cm ? cm : cn; }
template<typename T>void Min(T &cn, T cm) {cn = cn < cm ? cn : cm; }
int n, k;
char c[MAXN+1];
LL f[MAXN+1][MAXN+1][3];
LL lei[MAXN+1];
void getit(char c[], int &clen)
{
while(!isalpha(c[1] = getchar())); clen = 1;
while(isalpha(c[++clen] = getchar())); clen--;
}
signed main()
{
// freopen("string.in","r",stdin);
// freopen("string.out","w",stdout);
Read(n); Read(k);
getit(c, n);
for(int i = 0;i<=n+1;i++) for(int j = 0;j<=k;j++) f[i][j][0] = f[i][j][1] = f[i][j][2] = 0;
for(int i = 1;i<=n+1;i++) f[i][0][1] = 1;
memset(lei,0,sizeof(lei));
for(int i = n;i>=1;i--) for(int j = 0;j<=k;j++)
{
f[i][j][0] = 1ll*(c[i]-'a')*(f[i+1][j][0] + f[i+1][j][1] + f[i+1][j][2])%MOD;
f[i][j][1] = (lei[j] + f[i][j][1])%MOD;
int lin = j-(n-i+1);
if(lin>=0) {
f[i][j][2] = 1ll*('z'-c[i])*(f[i+1][lin][0] + f[i+1][lin][1] + f[i+1][lin][2])%MOD;
for(int ij = i-1, ik = j+(n-i+1);ij>=1 && ik <= k;ij--, ik = ik+(n-i+1)) f[ij][ik][1] = (f[ij][ik][1] + f[i][j][2])%MOD;
}
lei[j] = (lei[j] + f[i][j][0])%MOD;
}
// for(int i = n;i>=1;i--) for(int j = 0;j<=k;j++) printf("f[%d][%d] : %d %d %d
",i,j,f[i][j][0],f[i][j][1],f[i][j][2]);
Write((f[1][k][0] + f[1][k][1] + f[1][k][2])%MOD); puts("");
return 0;
}