ZUFE 问题 R: kiminonamaewa

ZUFE 问题 R: kiminonamaewa"/>

ZUFE 问题 R: kiminonamaewa

比较难的区间dp题

#include<bits/stdc++.h>using namespace std;long long  dp[60][60];
int mm = 1e9 + 7;int main()
{int T , n ;string s;cin >> T;while(T --){cin >> n;cin >> s;memset(dp,0,sizeof(dp));for(int i = n - 1 ; i >= 0; i--){for(int j = i ; j < n ; j ++){dp[i][j] = (dp[i + 1][j] + dp[i][ j - 1 ] - dp[i + 1][j - 1]) % mm;if( s[i] == s[j])//dp[i][j] += (dp[i + 1][j - 1] + 1) % mm;dp[i][j] = (dp[i][j] + dp[i + 1][j - 1] + 1) % mm;}}dp[0][n-1] %= mm;cout << dp[0][n-1] << endl;}return 0;
}