/*
f[i][j]:表示[i, j]的最大合法子串长度
①:str[i] 和 str[j] 匹配
f[i][j] = f[i + 1][j - 1] + 2
②:str[i] 和 str[j] 不匹配(将区间缩小到两个端点可以匹配)
③:两种情况都要分区间
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int f[N][N];
char str[N];
int main() {
while (~scanf("%s", str + 1)) {
if (str[1] == 'e')
break;
memset(f, 0, sizeof f);
int n = strlen(str + 1);
for (int len = 2; len <= n; len ++ ) { // 长度
for (int i = 1; i + len - 1 <= n; i ++ ) { // 左端点
int j = i + len - 1;
if ((str[i] == '(' && str[j] == ')') || (str[i] == '[' && str[j] == ']'))
f[i][j] = max(f[i][j], f[i + 1][j - 1] + 2);
for (int k = i; k <= j; k ++ )
f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j]);
}
}
printf("%d\n", f[1][n]);
}
return 0;
}
/*
dp[i]:表示只看前i个字符从a串到b串的最少刷的次数
f[i][j]:表示从i到j的区间从a串到b串的最少刷的次数
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
char str1[N], str2[N];
int dp[N];
int f[N][N];
int main() {
while (~scanf("%s%s", str1, str2)) {
int n = strlen(str1);
memset(f, 0, sizeof f);
for (int i = 0; i < n; i ++ )
f[i][i] = 1;
for (int len = 2; len <= n; len ++ ) {
for (int i = 0; i + len - 1 < n; i ++ ) {
int j = i + len - 1;
f[i][j] = f[i + 1][j] + 1;
for (int k = i + 1; k <= j; k ++ )
if (str2[k] == str2[i])
f[i][j] = min(f[i][j], f[i + 1][k] + f[k + 1][j]);
}
}
memset(dp, 0, sizeof dp);
for (int i = 0; i < n; i ++ )
dp[i] = f[0][i];
for (int i = 0; i < n; i ++ ) {
if (str1[i] == str2[i]) {
if (!i)
dp[i] = 0;
else
dp[i] = dp[i - 1];
} else {
for (int k = 0; k < i; k ++ )
dp[i] = min(dp[i], dp[k] + f[k + 1][i]);
}
}
printf("%d\n", dp[n - 1]);
}
return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int a[N]; // 东西方向的车在时间为i，是否有车经过
int b[N]; // 存的是南北方向的车经过路口的时间
int n, m;
int main() {
while (~scanf("%d%d", &n, &m)) {
memset(a, 0, sizeof a);
memset(b, 0, sizeof b);
for (int i = 0; i < n; i ++ ) {
int x;
scanf("%d", &x);
a[x] = 1;
}
for (int i = 0; i < m; i ++ )
scanf("%d", &b[i]);
for (int w = 0; ; w ++ ) {
int flag = 0;
for (int i = 0; i < m; i ++ )
if (a[b[i] + w] == 1) { // 撞
flag = 1;
break;
}
if (!flag) {
printf("%d\n", w);
break;
}
}
}
return 0;
}
/*
f[i][j]:表示区间[i, j]的焦急程度
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, INF = 0x3f3f3f3f;
int f[N][N];
int arr[N];
int sum[N];
int n;
int casei;
int main() {
int T;
scanf("%d", &T);
while (T -- ) {
scanf("%d", &n);
memset(sum, 0, sizeof sum);
for (int i = 1; i <= n; i ++ ) {
scanf("%d", &arr[i]);
sum[i] = sum[i - 1] + arr[i];
}
memset(f, 0, sizeof f);
for (int i = 1; i <= n; i ++ )
for (int j = i + 1; j <= n; j ++ )
f[i][j] = INF;
for (int len = 2; len <= n; len ++ ) {
for (int i = 1; i + len - 1 <= n; i ++ ) {
int j = i + len - 1;
for (int k = i; k <= j; k ++ )
f[i][j] = min(f[i][j], f[i + 1][k] + f[k + 1][j] + arr[i] * (k - i) + (k - i + 1) * (sum[j] - sum[k]));
}
}
printf("Case #%d: %d\n", ++ casei, f[1][n]);
}
return 0;
}
/*
f[i][j][0]:表示给第i个人到第j个人送餐后，小哥在左端点
f[i][j][1]:表示给第i个人到第j个人送餐后，小哥在右端点
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010, INF = 0x3f3f3f3f;
int f[N][N][2];
int sum[N];
int n, v, p;
struct node {
int x, w;
bool operator<(const node &t)const {
return x < t.x;
}
} R[N];
int main() {
while (~scanf("%d%d%d", &n, &v, &p)) {
for (int i = 1; i <= n; i ++ )
scanf("%d%d", &R[i].x, &R[i].w);
n ++ ;
R[n].x = p, R[n].w = 0;
memset(sum, 0, sizeof sum);
sort(R + 1, R + 1 + n);
for (int i = 1; i <= n; i ++ )
sum[i] = sum[i - 1] + R[i].w;
int st;
memset(f, 0x3f, sizeof f);
for (int i = 1; i <= n; i ++ )
if (R[i].x == p) {
st = i;
break;
}
f[st][st][0] = f[st][st][1] = 0;
for (int i = st; i >= 1; i -- )
for (int j = st; j <= n; j ++ ) {
if (i == j)
continue;
f[i][j][0] = min(f[i][j][0], f[i + 1][j][1] + (sum[i] + sum[n] - sum[j]) * (R[j].x - R[i].x));
f[i][j][0] = min(f[i][j][0], f[i + 1][j][0] + (sum[i] + sum[n] - sum[j]) * (R[i + 1].x - R[i].x));
f[i][j][1] = min(f[i][j][1], f[i][j - 1][1] + (sum[i - 1] + sum[n] - sum[j - 1]) * (R[j].x - R[j - 1].x));
f[i][j][1] = min(f[i][j][1], f[i][j - 1][0] + (sum[i - 1] + sum[n] - sum[j - 1]) * (R[j].x - R[i].x));
}
printf("%d\n", min(f[1][n][0], f[1][n][1]) * v);
}
return 0;
}
/*
f[i][j]:表示第i天到第j天的最小服装量
①:第j天穿新衣服
f[i][j] = f[i][j - 1] + 1
②:第j天穿旧衣服
f[i][j] = f[i][k] + f[k + 1][j - 1]
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int f[N][N];
int arr[N];
int n;
int casei;
int main() {
int T;
scanf("%d", &T);
while (T -- ) {
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
scanf("%d", &arr[i]);
memset(f, 0, sizeof f);
for (int i = 1; i <= n; i ++ )
f[i][i] = 1;
for (int len = 2; len <= n; len ++ ) {
for (int i = 1; i + len - 1 <= n; i ++ ) {
int j = i + len - 1;
f[i][j] = f[i][j - 1] + 1;
for (int k = i; k < j; k ++ )
if (arr[k] == arr[j])
f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j - 1]);
}
}
printf("Case %d: %d\n", ++ casei, f[1][n]);
}
return 0;
}
