yukicoder No.10 - +か×か

Source

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

問題概要

$N$ 個の整数 $A_1,A_2,\ldots,A_N$ と整数 $T$ が与えられる.
$N$ 個の整数を,左結合で,足し算か掛け算をした時,$T$ になるようにしたい.
つまり,$(\cdots ((A_1\ {\rm op}_1\ A_2)\ {\rm op}_2\ A_3)\ {\rm op}_3 \cdots {\rm op}_{N-1}\ A_N) = T$ にしたい.
ただし,${\rm op}_k \in \{+,\times\}$.
このような ${\rm op}_1,{\rm op}_2,\ldots,{\rm op}_{N-1}$ を求める問題.
答えが存在することは保証されている.
ただし,答えが複数存在するなら,$+$ の方が $\times$ より小さいとして,辞書順最小のものを求める.

解法

動的計画法+経路復元.
状態として(何番目の整数まで使ったか,$x$)を取り,そこまでで $x$ が作れるかどうかを求めれば良い.
ここで,足し算と掛け算しかないので,値は減ることがなく,$x$ は $x \leq T$ の範囲のみ調べれば良い.
時間計算量,空間計算量ともに $O(NT)$.

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}

int N, T, A[51];
int dp[51][100001];

int main(){
  int i, j, k;

  reader(&N,&T);
  rep(i,N) reader(A+i);
  rep(j,T) dp[N][j] = 0; dp[N][T] = 1;
  for(i=N-1;i>=0;i--) rep(j,T+1){
    dp[i][j] = 0;
    if(j+A[i] <= T && dp[i+1][j+A[i]]) dp[i][j] = 1;
    if(j*A[i] <= T && dp[i+1][j*A[i]]) dp[i][j] = 1;
  }

  j = A[0];
  REP(i,1,N){
    if(j+A[i] <= T && dp[i+1][j+A[i]]){ mypc('+'); j += A[i]; continue; }
    if(j*A[i] <= T && dp[i+1][j*A[i]]){ mypc('*'); j *= A[i]; continue; }
  }
  mypc('\n');

  return 0;
}

Current time: 2017年07月23日15時47分26秒
Last modified: 2014年11月07日20時17分16秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン: