OJ Board

Code: Select all

#include <stdio.h>
#include <stdlib.h>
/* used to indicate which tracks are used for each possible solution */
unsigned int codes[] = { 0x80000, 0x40000, 0x20000, 0x10000, 0x8000, 0x4000, 0x2000, 0x1000, 0x800, 0x400, 0x200, 0x100, 0x80, 0x40, 0x20, 0x10, 0x8, 0x4, 0x2, 0x1};

int main() {
    unsigned int code, k,n, nTapeLength, nTracks;
    unsigned int tracks[20];
    unsigned int *sols;
    unsigned int nMaxFound;
    
    while (2 == scanf("%u %u", &nTapeLength, &nTracks)) {
		if (0 == nTracks) {
			puts("sum:0");
			continue;
		}
        sols = (unsigned int *)calloc(nTapeLength+1, sizeof(unsigned int));
        scanf("%u", tracks); 
        nMaxFound = tracks[0];
        sols[tracks[0]] = codes[0];
        
        for (n=1; n < nTracks; ++n) { 
            scanf("%u", tracks+n); 
            for (k=nMaxFound; k > 0; --k) {
                if (sols[k] > 0 && k+tracks[n] <= nTapeLength) {
                    code = sols[k] | codes[n];
                    if (sols[k+tracks[n]] < code) {
                        sols[k+tracks[n]] = code;
                        if (nMaxFound < k+tracks[n]) { nMaxFound = k+tracks[n]; }
                    } /* end of if a better solution was found */
                } /* end of if a solution was found */
            } /* end of for each possible solution */
            
            code = codes[n];
            if (sols[tracks[n]] < code) {
                sols[tracks[n]] = code;
                if (nMaxFound < tracks[n]) { nMaxFound = tracks[n]; }
            } 
        } /* end of for each number which needs to be read */
        
        for (n=nTapeLength; !sols[n]; --n) { ; }
        for (k=0; k < 20; ++k) {
            if (sols[n] & codes[k]) { printf("%u ", tracks[k]); }
        }
        printf("sum:%u\n", n);       
        free(sols);
    }
}

Code: Select all

#include <stdio.h>
#include <string.h>

int track[21];
int N,cnt;
int d[20000][21];

int dp(int cur, int s)
{
	int& ans = d[cur][s];
	if(ans)return ans;

	if(s == cnt) return 0;

	for(int i = s; i < cnt; i++)
	{
		if(cur >= track[i])
		{
			int t = dp(cur-track[i], i+1) + track[i];
			if(t > ans)ans = t;
		}
	}
	return ans;
}

int main()
{
	while(scanf("%d%d", &N, &cnt) != EOF)
	{
		for(int i = 0; i < cnt; i++)
		{
			scanf("%d", &track[i]);
		}
		memset(d, 0, sizeof(d));

		dp(N,0);
		int cur = N;
		// print answer
		for(int i = 0; i < cnt-1; i++)
		{
			for(int j = i; j < cnt; j++)
			{
				if(cur >= track[j])
				{
					if(d[cur][i] - d[cur-track[j]][j+1] == track[j])
					{
						printf("%d ",track[j]);
						cur = cur - track[j];
					}
				}
			}
		}
		if(cur >= track[cnt-1])printf("%d ", track[cnt-1]); // check the last 
		printf("sum:%d\n", d[N][0]);
	}
	return 0; 
}

Code: Select all

ac

Code: Select all

for input 
45 8 4 10 44 43 12 9 8 2

output 1: 4 10 12 9 8 2 sum:45
output 2:43 2 sum:45

Both are correct.

Code: Select all

#include <cstdio>
#include <algorithm>
#define MAX 20000

using namespace std;

long long tracks[MAX], resp[MAX];
long long current, N, n_tracks, sum, tam;
long long tab[MAX][MAX];

long long max(long long a, long long b){
    if(a > b)
        return a;
    return b;
}

long long print(long long n, long long W){
    long long indiceAtual = 0;
    long long linhaAtual = n;
    long long colunaAtual = W;
    while(linhaAtual != 0 && colunaAtual != 0){
        int num = tab[linhaAtual][colunaAtual];
        int sup = tab[linhaAtual - 1][colunaAtual];
        if(num == sup){
            linhaAtual--;
        }else{
	    resp[indiceAtual] = tracks[linhaAtual - 1];
	    indiceAtual++;
            colunaAtual = colunaAtual - tracks[linhaAtual - 1];
            linhaAtual--;
        }
    }
    return indiceAtual;
}

long long custo(long long n, long long W){
    for(long long i = 0; i <= n; i++)
        tab[i][0] = 0;
    for(long long i = 0; i <= W; i++)
        tab[0][i] = 0;
    for(long long i = 1; i <= n; i++){
    for(long long j = 1; j <= W; j++){
        if(tracks[i - 1] > j){
            tab[i][j] = tab[i-1][j];
        }else{
            tab[i][j] = max(tab[i-1][j], tracks[i - 1] + tab[i-1][j - tracks[i - 1]]);
        }
    }
    }
    return tab[n][W];
}

int main(){
    while(scanf("%lld", &N)!=EOF){
        scanf("%lld", &n_tracks);
    	sum = 0;
        for(long long i = 0; i < n_tracks; i++){
            scanf("%lld", &current);
            tracks[i] = current;
        }
        //sort(tracks, tracks + n_tracks + 2);
  	sum = custo(n_tracks, N);
  	tam = print(n_tracks, N);
   	for(long long i = tam - 1; i >= 0; i--)
		printf("%lld ", resp[i]);
	printf("sum:%lld\n", sum);
    }
    return 0;
}

Code: Select all

1 4 sum:5
8 2 sum:10
10 5 4 sum:19
10 23 1 2 3 4 5 7 sum:55
43 2 sum:45