明日は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");
    }
}