保存されている過去のバージョンの一覧

2020年12月05日15時24分50秒
2020年11月15日09時11分40秒

yukicoder No.1288 - yuki collection

Source

ニコニコミュニティ
問題文

問題概要

省略

解法

省略

cLay（version 20201205-1）のコード

C++に変換後のコードはこちら

int N;
char S[2002];
ll A[2000];
int ps[4], p[4][2001];
{
  int i, j, k;
  minCostFlow<int,ll> f;
  int node, st, ed;
  ll cost, flow;
  rd(N,S,A(N));

  node = N;
  st = node++;
  ed = node++;

  f.malloc(node);
  f.init(node);

  rep(i,N){
    if(S[i]=='y') p[0][ps[0]++] = i;
    if(S[i]=='u') p[1][ps[1]++] = i;
    if(S[i]=='k') p[2][ps[2]++] = i;
    if(S[i]=='i') p[3][ps[3]++] = i;
  }
  if(min(ps(4))==0) wt(0), return 0;

  f.addEdge(st, p[0][0], int_inf, 0LL);
  rep(i,ps[3]) f.addEdge(p[3][i], ed, 1, 1d9-A[p[3][i]]);
  rep(k,4) rep(i,1,ps[k]) f.addEdge(p[k][i-1], p[k][i], int_inf, 0LL);
  rep(k,3){
    j = 0;
    rep(i,ps[k]){
      while(j < ps[k+1] && p[k+1][j] < p[k][i]) j++;
      if(j == ps[k+1]) break;
      f.addEdge(p[k][i], p[k+1][j], 1, 1d9-A[p[k][i]]);
    }
  }

  f.solve(st, ed, flow, cost, -2, 4d9);
  wt(4d9*flow - cost);
}

cLay（version 20201115-1）のコード

C++に変換後のコードはこちら

int N;
char S[2002];
ll A[2000];
int ps[4], p[4][2001];
{
  int i, j, k;
  minCostFlow<int,ll> f;
  int node, st, ed;
  ll cost, flow, totcost = 0, totflow = 0, res = 0;
  rd(N,S,A(N));

  node = N;
  st = node++;
  ed = node++;

  f.malloc(node);
  f.init(node);

  rep(i,N){
    if(S[i]=='y') p[0][ps[0]++] = i;
    if(S[i]=='u') p[1][ps[1]++] = i;
    if(S[i]=='k') p[2][ps[2]++] = i;
    if(S[i]=='i') p[3][ps[3]++] = i;
  }
  if(min(ps(4))==0) wt(0), return 0;

  f.addEdge(st, p[0][0], int_inf, 0LL);
  rep(i,ps[3]) f.addEdge(p[3][i], ed, 1, 1d9-A[p[3][i]]);
  rep(k,4) rep(i,1,ps[k]) f.addEdge(p[k][i-1], p[k][i], int_inf, 0LL);
  rep(k,3){
    j = 0;
    rep(i,ps[k]){
      while(j < ps[k+1] && p[k+1][j] < p[k][i]) j++;
      if(j == ps[k+1]) break;
      f.addEdge(p[k][i], p[k+1][j], 1, 1d9-A[p[k][i]]);
    }
  }

  for(;;){
    f.solve(st, ed, flow, cost, 1);
    if(!flow) break;
    (totflow, totcost) += (flow, cost);
    res >?= 4d9 * totflow - totcost;
  }
  wt(res);
}

Current time: 2024年04月19日09時19分34秒
Last modified: 2020年12月05日15時24分50秒 (by laycrs)
Tags: Competitive_Programming_Incomplete yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン：