首页 > 代码库 > uva--242(邮资问题 dp)
uva--242(邮资问题 dp)
输入输出:
Sample Input
5 2 4 1 4 12 21 4 1 5 12 28 10 2 5 1 7 16 31 88 5 1 15 52 67 99 6 2 3 1 5 8 4 1 5 7 8 0
Sample Output
max coverage = 71 : 1 4 12 21 max coverage = 409 : 1 7 16 31 88 max coverage = 48 : 1 5 7 8
题意:
最多用S个邮票拼出最大连续数值,每组共同拥有N组例子,每组第一个是数组元素个数,输出字典序最小的一组。
用二维的状态事实上就能够了,i,j,k分别表示取到数组前i位用j个邮票能否拼出k,感觉有点像背包,输入并不都是排好序的,须要排序。
代码:
#include<iostream> #include<cstring> #include<cstdio> #include<map> #include<cstring> #include<vector> #include<algorithm> #define INF 0X3f3f3f3f #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long ll; typedef unsigned long long llu; const int maxd=10+5; int n,s; vector<int> st[maxd]; int dp[maxd][1005]; bool ok(int x) { for(int j=0; j<=s; ++j) if(dp[j][x]) return true; return false; } bool cmp(const vector<int> &a ,const vector<int> &b) { int lena=a.size(),lenb=b.size(); if(lena==lenb) for(int i=lena-1;i>=0;--i) if(a[i]!=b[i]) return a[i]<b[i]; return lena<lenb; } int solve(int x) { mem(dp,0); int len=st[x].size(); int c=st[x][len-1]*s; for(int j=0; j<=s; ++j) dp[j][0]=1; // for(int i=0; i<=len; ++i) dp[i][0][0]=1; for(int i=1; i<=len; ++i) { // memcpy(dp[i],dp[i-1],sizeof(dp[i])); for(int j=1; j<=s; ++j) { int w=j*st[x][i-1]; for(int m=j; m<=s; ++m) for(int k=w; k<=c; ++k) if(dp[m-j][k-w]) dp[m][k]=1; } } int ans=0; for(int i=1; i<=c; ++i) { if(ok(i)) ans=i; else break; } return ans; } int main() { freopen("1.txt","r",stdin); while(scanf("%d",&s)==1 && s) { scanf("%d",&n); for(int i=0; i<n; ++i) { int x,tmp; st[i].clear(); scanf("%d",&x); for(int j=0; j<x; ++j) scanf("%d",&tmp),st[i].push_back(tmp); sort(st[i].begin(),st[i].end()); } sort(st,st+n,cmp); int ans=0,pos=-1; for(int i=0; i<n; ++i) { int tmp=solve(i); // cout<<tmp<<endl; if(tmp>ans) { ans=tmp; pos=i; } } printf("max coverage =%4d :",ans); for(int i=0; i<st[pos].size(); ++i) printf("%3d",st[pos][i]); printf("\n"); } return 0; }
uva--242(邮资问题 dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。