/* O(K*S) solution devised by Bryce Sandlund and coded by Larry Pyeatt */ #include #include #include #define SIZE 5000 long long recurses=0; /* the table holds the minimum cost of making the sum from i to K be j */ int table[SIZE][SIZE]; /* [i][j] */ /* Find cost of changing A[i], A[i+K], A[i+2K],... to S. */ int immediate_cost(int *A,int N,int K, int i, int x) { int cost=0, j; for(j=i;j -1) */ /* return cost; */ /* if(i == 0) /\* First element in the array. *\/ */ /* { */ /* cost = immediate_cost(A,N,K,i,S); */ /* table[i][S]=cost; // put it in the table */ /* return cost; */ /* } */ /* // find minimum cost of changing elememnt i to 0..S */ /* cost = currcost = mincost(A,N,K,i-1,S) + immediate_cost(A,N,K,i,0); */ /* for(x = 1;x<=S;x++) */ /* { */ /* recurses++; */ /* currcost = mincost(A,N,K,i-1,S-x) + immediate_cost(A,N,K,i,x); */ /* if(currcost < cost) */ /* cost = currcost; */ /* } */ /* table[i][S]=cost; // enter value into table */ /* return cost; */ /* } */ /* find minimum cost of making the sum from i to K be j */ int mincost(int *A,int N,int K, int i, int j) { int cost,currcost,x; /* if it is in the table, just return the table value */ if((cost = table[i][j]) > -1) return cost; if(i == K) /* First element in the array. */ { cost = immediate_cost(A,N,K,i,j); table[i][j]=cost; // put it in the table return cost; } // find minimum cost of changing elememnt i to 0..j cost = currcost = mincost(A,N,K,i-1,j) + immediate_cost(A,N,K,i,0); for(x = 1;x<=j;x++) { recurses++; currcost = mincost(A,N,K,i-1,j-x) + immediate_cost(A,N,K,i,x); if(currcost < cost) cost = currcost; } table[i][j]=cost; // enter value into table return cost; } // Find pattern of length K which is S smooth, and will cause // the least number of changes when applied to entire array. int main() { static int A[SIZE]; int N,K,S,i,j,k,cost; if(scanf("%d%d%d",&N,&K,&S)!=3) { perror("unable to read N K S: "); exit(1); } for(i=0;i -1) min = table[i][jp]; table[i+1][j] = min; cost = mincost(A,N,K,0,S); printf("%d\n",cost); // printf("%lld\n",recurses); return 0; }