1R/2016 10 08

오늘의 문제

• 합 구하기 4
• 합 구하기
• [1]

참가자

• 15이원준

코드

15이원준

구간 합 구하기 4

#include<iostream>

using namespace std;

long long int arr[4000000] = { 0, };
int start = 1;

int sort(int n){
  while(n){
    int p = (n-1) / 2;
    if(n%2){
      arr[p] = arr[n] + arr[(p+1)*2];
    }
    else{
      arr[p] = arr[n] + arr[(p+1)*2 - 1];
    }
    n = p;
  }
}
long long int initSort(int n){
  if(n >= start){
    return arr[n];
  }
  if(arr[n]){
    if(arr[n] == -1){
      return 0;
    }
    return arr[n];
  }
  long long int tmp1 = initSort((n+1)*2);
  long long int tmp2 = initSort((n+1)*2 -1);
  long long int tmp = tmp1 + tmp2;
  if(tmp  == 0){
    arr[n] = -1;
    return 0;
  }
  return arr[n] = tmp;
}
long long int sum(int s, int e){
  long long int ans = 0;
  while(s < e){
    if(s%2){
      s = (s-1)/2;
    }
    else{
      ans += arr[s];
      s = s/2;
    }
    if(e%2){
      ans += arr[e];
      e = (e-2)/2;
    }
    else{
      e = (e-1)/2;
    }
  }
  if(s == e){
    ans += arr[s];
  }
  return ans;
}


int main(){
  int n,m,k;
  cin>>n>>m;
  while(n > start){
    start *= 2;
  }
  start -= 1;
  for(int i = 0; i<n; i++){
    scanf("%d",&arr[start + i]);
  }
  initSort(0);
  for(int i = 0; i< m; i++){
    int tmp1, tmp2;
    scanf("%d %d", &tmp1, &tmp2);
    printf("%lld\n", sum(start-1 + tmp1, start-1+tmp2));
  }
}

구간 합 구하기

#include<iostream>

using namespace std;

long long int arr[4000000] = { 0, };
int start = 1;

void sort(int n){
  while(n){
    int p = (n-1) / 2;
    if(n%2){
      arr[p] = arr[n] + arr[n+1];
    }
    else{
      arr[p] = arr[n] + arr[n-1];
    }
    n = p;
  }
}
long long int initSort(int n){
  if(n >= start){
    return arr[n];
  }
  if(arr[n]){
    if(arr[n] == -1){
      return 0;
    }
    return arr[n];
  }
  long long int tmp1 = initSort((n+1)*2);
  long long int tmp2 = initSort((n+1)*2 -1);
  long long int tmp = tmp1 + tmp2;
  if(tmp  == 0){
    arr[n] = -1;
    return 0;
  }
  return arr[n] = tmp;
}
long long int sum(int s, int e){
  long long int ans = 0;
  while(s < e){
    if(s%2){
      s = (s-1)/2;
    }
    else{
      ans += arr[s];
      s = s/2;
    }
    if(e%2){
      ans += arr[e];
      e = (e-2)/2;
    }
    else{
      e = (e-1)/2;
    }
  }
  if(s == e){
    ans += arr[s];
  }
  return ans;
}

int main(){
  int n,m,k;
  cin>>n>>m>>k;
  while(n > start){
    start *= 2;
  }
  start -= 1;
  for(int i = 0; i<n; i++){
    scanf("%d",&arr[start + i]);
  }
  initSort(0);

  for(int i = 0; i< m+k; i++){
    int tmp1, tmp2, tmp3;
    scanf("%d %d %d", &tmp1, &tmp2, &tmp3);
    if(tmp1 == 1){
      arr[start + tmp2 -1] = tmp3;
      sort(start + tmp2 -1);
    }
    else{
      printf("%lld\n", sum(start-1 + tmp2, start-1+tmp3));
    }
  }
}

자두나무

#include<iostream>
#include<algorithm>

using namespace std;

int arr[32][1001] = {0,};
int ina[1001] = {0,};
int main(){
  int n, m;
  cin>>n>>m;
  for(int i = 1; i<=n; i++){
    scanf("%d", &ina[i]);
  }
  int place = 1;
  for(int i = 1; i<=m+1; i++){
    for(int j = 1; j<=n; j++){
      int tmp = arr[i][j-1];
      if(ina[j] == place){
        tmp++;
      }
      arr[i][j] = max(tmp, arr[i-1][j]);
    }
    if(i%2){
      place = 2;
    }
    else{
      place = 1;
    }
  }

  cout<<arr[m+1][n];

}

아이디어

15이원준

• 구간합은 Binary Indexed Tree를 사용했습니다.
• 자두나무는 dp로 풀었습니다.(냅색을 약간 응용했습니다.)