といたやつメモ

3036

メモ化再帰
DPっていわれるといわゆるループの方しか思い浮かばなくて発想が固くなってたけどよく考えたらこの再帰って自明

#include <cstdio>
int dx[]={-1,0,-1,1,0,1};
int dy[]={-1,-1,0,0,1,1};
int memo[15][15][15];
int dfs(int x, int y, int cnt) {
    if (x==7&&y==7&&cnt==0) return 1;
    else if (cnt==0) return 0;
    if (memo[x][y][cnt]!=-1) return memo[x][y][cnt];
    int res=0;
    for (int i=0; i<6; i++) {
        int nx=x+dx[i], ny=y+dy[i];
        if (nx>=0&&nx<=14&&ny>=0&&ny<=14) {
            res += dfs(nx,ny,cnt-1);
        }
    }
    return memo[x][y][cnt]=res;
}
int main() {
    int t; scanf("%d",&t);
    for (int ix=0; ix<t; ix++) {
        int n; scanf("%d",&n);
        for (int i=0; i<15; i++) for (int j=0; j<15; j++) for (int k=0; k<15; k++) {
            memo[i][j][k]=-1;
        }
        printf("%d\n",dfs(7,7,n));
    }
}

chokudai dpイメージ練習１

ちょっとやってみた。
貪欲の問題としては有名な以下の問題をDPで解くと・・・？という話。

100万円以下の金額が与えられる。日本の硬貨／紙幣で支払いをする時、支払う合計枚数の最小値を出力しなさい

ためしにやってみた。

#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;
/*
100万円以下の金額が与えられる。日本の硬貨／紙幣で支払いをする時、支払う合計枚数の最小値を出力しなさい
*/
/*
1<=n<=10^7
1,5,10,50,100,1000,5000,10000
*/
int dp[1000001];
int coin[8]={1,5,10,50,100,1000,5000,10000};
int main() {
    fill(dp, dp+1000001, INT_MAX/2);
    dp[0]=0;
    for (int i=0; i<8; i++) dp[coin[i]]=1;
    for (int i=2; i<1000001; i++) {
        for (int j=0; j<8; j++) {
            if (i-coin[j]>=0) {
                dp[i]=min(dp[i], dp[i-coin[j]]+1);
            } else break;
        }
    }
    int n;
    while (scanf("%d",&n)) {
        if (n==-1) break;
        printf("%d\n",dp[n]);
    }
}

多分これでヨカ

2029

座標にある変なものを指定された横と縦の長さをもつ長方形で囲んでみたとき一番多く変なものを囲めるときの変なものの最大値。
普通に探索

#include <cstdio>
#include <algorithm>
using namespace std;
int mat[100][100];
int n, w, h, s, t;
int cnt(int x1, int y1, int x2, int y2) {
    int res=0;
    for (int i=x1; i<x2; i++)
        for (int j=y1; j<y2; j++) res+=mat[i][j];
    return res;
}
int main() {
    while (scanf("%d",&n)) {
        if (!n) break;
        scanf("%d%d",&w,&h);
        for (int i=0; i<h; i++) for (int j=0; j<w; j++) mat[i][j]=0;
        for (int i=0; i<n; i++) {
            int x,y; scanf("%d%d",&x,&y);
            mat[y-1][x-1]=1;
        }
        scanf("%d%d",&s,&t);
        int res=0;
        for (int i=0; i<=h-t; i++) {
            for (int j=0; j<=w-s; j++) {
                res=max(res, cnt(i,j,i+t,j+s));
            }
        }
        printf("%d\n",res);
    }
}

2683

ACM/ICPC予選突破の手引きにも解法が文章読解と書いてある実装するだけの問題

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
ll tanri(ll s, int y, double rate, int cost) {
    int sum=0;
    for (int i=0; i<y; i++) {
        sum+=floor(s*rate);
        s-=cost;
    }
    return sum+s;
}
ll fukuri(ll s, int y, double rate, int cost) {
    for (int i=0; i<y; i++) {
        int b=floor(s*rate);
        s+=b-cost;
    }
    return s;
}
int main() {
    int m;
    scanf("%d",&m);
    for (int ix=0; ix<m; ix++) {
        ll s;
        int y, n;
        scanf("%lld%d%d",&s,&y,&n);
        ll res=0;
        for (int i=0; i<n; i++) {
            int type, cost;
            double rate;
            scanf("%d%lf%d",&type,&rate,&cost);
            if (type) res=max(res,fukuri(s,y,rate,cost));
            else res=max(res, tanri(s,y,rate,cost));
        }
        printf("%lld\n",res);
    }
}

1157

DP表から必死にイメージしやすいもの探してたらIOIの過去問でこれがあった。
最初花を全種類使わなければならないことを失念していて１WA。。。
これはあらかじめなんかデータとして表が与えられるのでDPへの変換もわりと頭使わずに直感で出来ちゃいます。

#include <cstdio>
#include <algorithm>
using namespace std;
const int INF=-100000;
int table[102][102];
int dp[102][102];
int main() {
    int f, v;
    for (int i=0; i<102; i++) for (int j=0; j<102; j++) dp[i][j]=INF;
    scanf("%d%d",&f,&v);
    for (int i=0; i<f; i++) for (int j=0; j<v; j++) scanf("%d",&table[i][j]);
    for (int i=0; i<v-f+1; i++) dp[0][i]=table[0][i];
    for (int i=1; i<f; i++) {
        for (int j=i; j<v-f+1+i; j++) {
            for (int k=0; k<j; k++) if (dp[i-1][k]!=INF)
                dp[i][j]=max(dp[i][j],dp[i-1][k]+table[i][j]);
        }
    }
    int res=INF;
    for (int i=0; i<v; i++) res=max(res, dp[f-1][i]);
    printf("%d\n",res);
}