読者です 読者をやめる 読者になる 読者になる

夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

斎戒

DP斎戒

AOJ 2197

DPじゃないやん(バシッ

#include <cstdio>
int cnt[1001];
int main() {
    int n;
    for (int i=1; i<=1000; i++) {
        int sum=i;
        for (int j=i+1;; j++) {
            sum+=j;
            if (sum>1000) break;
            cnt[sum]++;
        }
    }
    while (scanf("%d",&n)) {
        if (!n) break;
        printf("%d\n",cnt[n]);
    }
}

PKU 1036

どうやら同時に複数人のgangが入れたらしい・・・
いろいろ最後の詰でいじめられた

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
int n, k, tl;
int t[100], p[100], s[100];
int dp[2][101];
int main() {
    scanf("%d%d%d",&n,&k,&tl);
    for (int i=0; i<n; i++) scanf("%d",&t[i]);
    for (int i=0; i<n; i++) scanf("%d",&p[i]);
    for (int i=0; i<n; i++) scanf("%d",&s[i]);
    vector<vector<int> > gangs(tl+1);
    for (int i=0; i<n; i++) {
        if (gangs[t[i]].empty()) {
            gangs[t[i]]=vector<int>(k+1);
        }
        gangs[t[i]][s[i]]+=p[i];
    }
    for (int i=0; i<2; i++) {
        for (int j=0; j<=k; j++) dp[i][j]=-99999;
    }
    dp[0][0]=0;
    for (int i=1; i<=tl; i++) {
        for (int j=0; j<=k; j++) {
            if (j-1>=0) dp[i&1][j]=max(dp[i&1][j],dp[(i-1)&1][j-1]);
            dp[i&1][j]=max(dp[i&1][j],dp[(i-1)&1][j]);
            if (j+1<=k) dp[i&1][j]=max(dp[i&1][j],dp[(i-1)&1][j+1]);
            if (!gangs[i].empty()) dp[i&1][j]+=gangs[i][j];
        }
    }
    int res=0;
    for (int i=0; i<=k; i++) res=max(res,dp[tl&1][i]);
    printf("%d\n",res);
}

AOJ 0202

これはこれで計算量すくなくなるはずの実装でバグっていじめられた

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAX 1000001
using namespace std;
int n, x;
int isprime[MAX];
int w[30];
int dp[MAX];
int main() {
    memset(isprime, 1, sizeof(isprime));
    isprime[0]=isprime[1]=0;
    for (int i=2; i<MAX; i++) {
        if (isprime[i]) {
            for (int j=i*2; j<MAX; j+=i) isprime[j]=0;
        }
    }
    while (scanf("%d%d",&n,&x)) {
        if (n==0&&x==0) break;
        memset(dp, 0, sizeof(dp));
        for (int i=0; i<n; i++) scanf("%d",&w[i]);
        dp[0]=1;
        for (int i=0; i<=x; i++) {
            if (dp[i]) {
                for (int j=0; j<n; j++) {
                    if (i+w[j]<=x) dp[i+w[j]]=1;
                }
            }
        }
        int res=-1;
        for (int i=x; i>0; i--) {
            if (dp[i]&&isprime[i]) {
                res=i;
                break;
            }
        }
        if (res==-1) puts("NA");
        else printf("%d\n",res);
    }
}
広告を非表示にする