PKU 3444-Wavelet Compression
問題概要
数列をある条件でエンコードしたものが与えられる。デコードせよ。
解法
逆から考えて実装する
実装(C)
#include <stdio.h> #include <stdlib.h> int n,i,j; int input[300]; void decode(int x){ if(x>=n)return; int d[300]; for(i=0;i<x;i++){ d[2*i]=(input[i]+input[i+x])/2; d[2*i+1]=(input[i]-d[2*i]); } for(i=0;i<2*x;i++){ input[i]=d[i]; } decode(x*2); } int main(void) { while(scanf("%d",&n),n){ for(i=0;i<n;i++)scanf("%d",&input[i]); decode(1); for(i=0;i<n;i++){ if(i)putchar(' '); printf("%d",input[i]); } puts(""); } }