bzoj 1296: [SCOI2009] 브러시 장인
1 #include
2 #define LL long long
3 #define fi first
4 #define se second
5 #define mk make_pair
6 #define pii pair
7 #define piii pair>
8
9 using namespace std;
10
11 const int N = 50 + 7;
12 const int M = 1e4 + 7;
13 const int inf = 0x3f3f3f3f;
14 const LL INF = 0x3f3f3f3f3f3f3f3f;
15 const int mod = 1e9 + 7;
16
17 char s[N][N];
18 int f[N][N][2], dp[N][2501], v[N][N], n, m, t;
19 int main() {
20 scanf("%d%d%d", &n, &m, &t);
21 for(int i = 1; i <= n; i++)
22 scanf("%s", s[i] + 1);
23
24 for(int k = 1; k <= n; k++) {
25 memset(f, 0, sizeof(f));
26 for(int i = 1; i <= m; i++) {
27 for(int j = 1; j <= m; j++) {
28 f[i][j][0] = f[i - 1][j][0];
29 f[i][j][1] = f[i - 1][j][1];
30
31 if(s[k][i] == '1') {
32 f[i][j][1] = max(f[i][j][1], f[i - 1][j][1] + 1);
33 f[i][j][1] = max(f[i][j][1], f[i - 1][j - 1][0] + 1);
34 } else {
35 f[i][j][0] = max(f[i][j][0], f[i - 1][j][0] + 1);
36 f[i][j][0] = max(f[i][j][0], f[i - 1][j - 1][1] + 1);
37 }
38 }
39
40 }
41 for(int j = 1; j <= m; j++) {
42 v[k][j] = max(f[m][j][0], f[m][j][1]);
43 v[k][j] = max(v[k][j], v[k][j - 1]);
44 }
45 }
46
47 int ans = 0;
48 for(int i = 1; i <= n; i++) {
49 for(int j = 1; j <= t; j++) {
50 for(int k = 0; k <= m && j - k >= 0; k++) {
51 dp[i][j] = max(dp[i][j], dp[i - 1][j - k] + v[i][k]);
52 }
53 ans = max(ans, dp[i][j]);
54 }
55 }
56
57 printf("%d
", ans);
58 return 0;
59 }
60
61 /*
62 */
전재 대상:https://www.cnblogs.com/CJLHY/p/9064337.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.