//有多个订单方案,运输公司可以选择接受订单也可以不接受,但必须保证不要超载(限载量是n),使得运输公司赚钱最多,输出赚最多的钱数。 2.2秒险过
#include<stdio.h> #include<string.h> #include<ctype.h> #include<stdlib.h> #include<math.h> int n,m,k,maxn; int a[30][5],vis[30],num[30][30]; void dfs(int x) { int i,ok=1,sum,temp; if(x==k) { sum=0; for(i=0;i<k;i++) { if(vis[i]) sum+=(a[i][1]-a[i][0])*a[i][2]; } if(sum>maxn) maxn=sum; return ; } for(i=a[x][0];i+1<=a[x][1];i++) { temp=num[i][i+1]; temp+=a[x][2]; if(temp>n) { ok=0; break; } } if(ok) { vis[x]=1; for(i=a[x][0];i+1<=a[x][1];i++) num[i][i+1]+=a[x][2]; dfs(x+1); for(i=a[x][0];i+1<=a[x][1];i++) num[i][i+1]-=a[x][2]; } vis[x]=0; dfs(x+1); } main() { int i,count=1; //freopen("D:\\in.txt","r",stdin); while(scanf("%d%d%d",&n,&m,&k)&&n+m+k) { memset(vis,0,sizeof(vis)); memset(num,0,sizeof(num)); for(i=0;i<k;i++) scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]); maxn=0; dfs(0); printf("%d\n",maxn); } return 0; }