QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#509775 | #1974. Black Family Tree | PetroTarnavskyi# | WA | 0ms | 113736kb | C++20 | 1.8kb | 2024-08-08 18:34:30 | 2024-08-08 18:34:30 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
const int N = 304;
const int INF = 1e9 + 7;
int dp1[N][N][N];
int dp2[N][N];
string s;
void updMin(int& a, int b)
{
a = min(a, b);
}
void calc(int i)
{
int n = SZ(s);
dp1[i][0][0] = 0;
FOR (lenL, 0, i + 1)
{
FOR (lenR, 0, n - i)
{
if (lenL < i)
updMin(dp1[i][lenL + 1][lenR], dp1[i][lenL][lenR] + 1);
if (lenR < n - i - 1)
updMin(dp1[i][lenL][lenR + 1], dp1[i][lenL][lenR] + 1);
if (lenL < i && lenR < n - i - 1 && s[i - lenL + 1] == s[i + lenR])
updMin(dp1[i][lenL + 1][lenR + 1], dp1[i][lenL][lenR]);
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
FOR (i, 0, N) FOR (j, 0, N)
{
dp2[i][j] = INF;
fill(dp1[i][j], dp1[i][j] + N, INF);
}
cin >> s;
int n = SZ(s);
FOR (i, 0, n)
calc(i);
//FOR (i, 0, n)
//{
// FOR (lenL, 0, i + 1)
// {
// FOR (lenR, 0, n - i)
// cerr << i << ' ' << lenL << ' ' << lenR << ' ' << dp1[i][lenL][lenR] << '\n';
// }
//}
//return 0;
dp2[0][0] = 0;
FOR (i, 0, n)
{
FOR (len, 0, i + 1)
{
FOR (len2, 0, n - i + 2)
{
updMin(dp2[i + len2][len2], dp2[i][len] + dp1[i][len][len2] + 1);
}
}
}
FOR (i, 0, n + 1)
{
FOR (len, 0, i + 1)
cerr << i << ' ' << len << ' ' << dp2[i][len] << '\n';
}
int ans = INF;
FOR (i, 0, n + 1)
updMin(ans, dp2[n][i]);
cout << ans << '\n';
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 113736kb
input:
6 5 1 2 4 8 16 32 1 2 2 1 5 1 1 2 3 4 5 2 6 6 6
output:
1000000007
result:
wrong answer 1st lines differ - expected: '63', found: '1000000007'