| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
O(n)的简单动态规划解法,题目中有一个地方没有说清楚,就是1,2,3不一定都要出现#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <stack>
#include <algorithm>
#include <functional>
#include <iostream>
#include <cmath>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f
int main() {
int N;
scanf("%d", &N);
vector<int> data;
data.resize(N);
for (int i = 0; i < N; ++i) {
scanf("%d", &data[i]);
}
int dp[2][3];
memset(dp, 0x3f, sizeof(dp));
for (int i = 0; i < N; ++i) {
if (i == 0) {
for (int j = 0; j < 3; ++j) {
if (j + 1 == data[i]) {
dp[0][j] = dp[1][j] = 0;
} else {
dp[0][j] = dp[1][j] = 1;
}
}
} else {
for (int j = 2; j >= 0; --j) {
dp[0][j] = j > 0 ? min(dp[0][j - 1], dp[0][j]) : dp[0][j];
dp[0][j] = j > 1 ? min(dp[0][j - 2], dp[0][j]) : dp[0][j];
dp[0][j] += (j + 1 != data[i]);
}
for (int j = 0; j <= 2; ++j) {
dp[1][j] = j < 2 ? min(dp[1][j + 1], dp[1][j]) : dp[1][j];
dp[1][j] = j < 1 ? min(dp[1][j + 2], dp[1][j]) : dp[1][j];
dp[1][j] += (j + 1 != data[i]);
}
}
}
int res = INF;
for (int i = 0; i < 3; ++i) {
int temp = min(dp[0][i], dp[1][i]);
res = min(temp, res);
}
printf("%d\n", res);
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator