ZOJ - 3777 && ZOJ - 2972（dp )

待我称王封你为后i 2022-05-26 03:39 180阅读 0赞

这两个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;
    }