Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

O(n)的简单动态规划解法,题目中有一个地方没有说清楚,就是1,2,3不一定都要出现

Posted by zxj1015 at 2015-05-04 21:50:58 on Problem 3670
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator