JOI春合宿2014 Day4-3 Straps

解法

みた感じDPだけど微妙に出来なみがあるDP。ちょっと考えて、
dp[i][j]: i番目のストラップまで見たときに、残り端子数がj個のときの嬉しさの最大値
と定義してあげると上手くいく。
jが負値になる(=端子がj個足りない)ことがあるので、配列外参照しないようにいい感じにやる。
初期状態がdp[0][N + 1] ← 0としてあるのは、そのため。N個くらい以上端子が足りなくなったら絶望だからそこら辺にずらしておく。

ソース

#include<bits/stdc++.h>
using namespace std;
const int INF = 1 << 30;

int dp[2][4001]; //ストラップ接続数の余裕
int N, A[2000], B[2000];
int main(){

  cin >> N;
  for(int i = 0; i < N; i++){
    cin >> A[i] >> B[i];
  }
  fill_n( *dp, 2 * 4001, -INF);
  dp[0][N + 1] = 0;
  for(int i = 0; i < N; i++){
    for(int j = 0; j <= 2 * N; j++){
      if(dp[i&1][j] == -INF || j + A[i] - 1 < 0) continue;
      dp[(i + 1)&1][j] = max(dp[(i + 1)&1][j], dp[i&1][j]);
      dp[(i + 1)&1][min( 2 * N, j + A[i] - 1)] = max( dp[(i + 1)&1][min( 2 * N, j + A[i] - 1)], dp[i&1][j] + B[i]);
    }
  }
  cout << *max_element( dp[N & 1] + N, dp[N & 1] + 2 * N + 1) << endl;
}

JOI春合宿2014 Day1-2 Growing Vegetables is Fun

解法

この問題いろいろなコンテストで再出題されてる気がする。
その草を昇順降順に並べたときのコストをBIT使って素早く求めておいて、 その情報を元にそのIOI草を左か右どっちに配置するか比べる。

ソース

#include<bits/stdc++.h>  
using namespace std;
const int INF = 1 << 30;

struct BIT{
  vector< int > bit;
  size_t sz;
  int sum(int idx){
    int sum = 0;
    for( ; idx ; idx -= idx & -idx) sum += bit[idx];
    return sum;
  }
  void add(int idx, int value){
    for( ; idx < bit.size(); idx += idx & -idx) bit[idx] += value;
  }
  BIT(int size):sz(size){
    bit.resize(size, 0);
  };
};
typedef pair< int , int > Pi;
int main(){
  int n;
  cin >> n;
  vector< int > vc(n);
  vector< Pi > cp(n);
  BIT bit1(n + 1), bit2(n + 1);
  for(int i = 0; i < n; ++i){
    scanf("%d", &vc[i]);
    cp[i] = make_pair( vc[i], i);
  }
  sort( cp.begin(), cp.end());

  int cnt = 1;
  for(int i = 0; i < cp.size(); ){
    do{
      vc[cp[i].second] = cnt;
      ++i;
    } while(i < cp.size() && cp[i - 1].first == cp[i].first);
    ++cnt;
  }

  BIT& b = bit1;
  vector< int > hoge[2];
  for(int j = 0; j < 2; ++j){
    hoge[j].resize(n);
    for(int i = 0; i < n; ++i){
      hoge[j][i] = i - bit1.sum(vc[i]);
      bit1.add( vc[i], 1);
    }
    reverse( vc.begin(), vc.end());
    b = bit2;
  }
  long long count = 0;
  for(int i = 0; i < n; ++i){
    count += min( hoge[0][i], hoge[1][n - 1 - i]);
  }
  printf("%lld\n", count);
}