ZOJ - 3777 && ZOJ - 2972（dp )-蒲公英云

ZOJ - 3777 && ZOJ - 2972（dp )

这两个dp感觉非常类似，都是dfs会超时，利用上一层和下一层关系， dp做出来

zoj 2972

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const double ep=1e-10;
const int INF=0x3f3f3f3f;
int n, m;
struct node {
    int t1, t2, t3, c1, c2;
} lan[120];
int dp[120][120];
int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        memset(dp, 0x3f, sizeof(dp));
        scanf("%d%d", &n, &m);
        for(int i=1; i<=n; i++)
            scanf("%d%d%d%d%d", &lan[i].t1, &lan[i].t2, &lan[i].t3, &lan[i].c1, &lan[i].c2);
        dp[0][m]=0;
        for(int i=1; i<=n; i++) {
            for(int j=0; j<=m; j++) {
                if(m>=j+lan[i].c1)
                    dp[i][j]=min(dp[i][j], dp[i-1][j+lan[i].c1]+lan[i].t1);
                dp[i][j]=min(dp[i][j], dp[i-1][j]+lan[i].t2);
                int tmp=min(m, j+lan[i].c2);
                dp[i][tmp]=min(dp[i][tmp], dp[i-1][j]+lan[i].t3);
            }
        }
        int ans=INF;
        for(int i=0; i<=m; i++)
            ans=min(dp[n][i], ans);
        printf("%d\n", ans);
    }
    return 0;
}

zoj 3777

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
int p[15][15];
ll dp[1<<13][600];
ll fact(ll n){
    ll ans=1;
    for(ll i=1; i<=n; i++)
        ans*=i;
    return ans;
}
ll gcd(ll a, ll b){
    return b==0 ? a : gcd(b, a%b);
}
int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        memset(dp, 0, sizeof(dp));
        int n, m;
        scanf("%d%d", &n, &m);
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                scanf("%d", &p[i][j]);
        dp[0][0]=1;
        for(int i=0; i<(1<<n); i++)
        {
            int tmp=1;
            for(int j=0; j<n; j++)
                if(i&(1<<j)) tmp++;
            for(int j=1; j<=n; j++)
            {
                if(i&(1<<(j-1))) continue;
                for(int k=0; k<=m; k++)
                {
                    if(k+p[tmp][j]>=m)
                        dp[(i|(1<<(j-1)))][m]+=dp[i][k];
                    else
                        dp[(i|(1<<(j-1)))][k+p[tmp][j]]+=dp[i][k];
                }
            }
        }
        if(dp[(1<<n)-1][m]!=0)
        {
            ll t1=fact(n), t2=dp[(1<<n)-1][m], t3=gcd(t1, t2);
            printf("%lld/%lld\n", t1/t3, t2/t3);
        }    
        else
            printf("No solution\n");
    }
    return 0;
}