夢追い人

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

明日はSPEC〜翔

みよう

0537

問題の言い換えは自力
DPの概要も自力
でもメモリをうまくけずれなかったのでそこはぐぐって参考にした

#include <cstdio>
#include <cstring>
#define mod 100000
int n, m, s;
int dp[3001][50];
int main() {
    while (scanf("%d%d%d",&n,&m,&s)) {
        if (!n&&!m&&!s) break;
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for (int i=1; i<=m; i++) {
            for (int j=n*n; j>0; j--) {
                for (int k=s; k>=i; k--) {
                    dp[k][j]=(dp[k][j]+dp[k-i][j-1])%mod;
                }
            }
        }
        printf("%d\n",dp[s][n*n]);
    }
}

0154

ループの向きって難しいね

#include <cstdio>
#include <cstring>
typedef long long ll;
int m, g;
int a[7], b[7];
ll dp[8][1001];
int main() {
    while (scanf("%d",&m)) {
        if (!m) break;
        for (int i=0; i<m; i++) scanf("%d%d",&a[i],&b[i]);
        memset(dp, 0, sizeof(dp));
        dp[0][0]=1;
        for (int i=0; i<m; i++) {
            for (int k=0; k<=1000; k++) {
                for (int j=0; j<=b[i]; j++) {
                    if (k+a[i]*j>1000) continue;
                    dp[i+1][k+a[i]*j]+=dp[i][k];
                }
            }
        }
        scanf("%d",&g);
        for (int i=0; i<g; i++) {
            int n; scanf("%d",&n);
            printf("%lld\n",dp[m][n]);
        }
    }
}

1035

やるだけなのにばぐらせまくってた

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int w, q;
int there[101];
int main() {
    while (scanf("%d%d",&w,&q)) {
        if (!w&&!q) break;
        memset(there, -1, sizeof(there));
        for (int i=0; i<q; i++) {
            char c; cin>>c;
            if (c=='s') {
                int id, cw; scanf("%d%d",&id,&cw);
                int b=-1;
                for (int j=0; j<w; j++) {
                    if (there[j]!=-1) continue;
                    int cnt=0, temp=j;
                    while (j<w&&there[j]==-1) {
                        j++; cnt++;
                    }
                    if (cnt>=cw) {
                        b=temp;
                        for (int k=b; k<b+cw; k++) there[k]=id;
                        break;
                    }
                }
                if (b==-1) puts("impossible");
                else printf("%d\n",b);
            } else {
                int id; scanf("%d",&id);
                for (int j=0; j<w; j++) if (there[j]==id) there[j]=-1;
            }
        }
        puts("END");
    }
}

さぁGoでもやろう

広告を非表示にする