Transportation-POJ 1040

本文主要是介绍Transportation-POJ 1040，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

DFS练习题，直接暴力吧，600+MS过的。。。。不能DP，有后效性，还有以后少用memcpy了，复杂度好大。。。。。

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int max_size,n,m;
#define MAXD 100 + 10
#define max(a,b) (a > b? a: b)
int state[MAXD];
int ans;
struct Route{int x;int y;int per;
}Stop[MAXD];
void solve(int u,int money){if(u == m){ans = max(ans,money);return ;}solve(u + 1,money);  /*不选择这个订单*/int x = Stop[u].x;int y = Stop[u].y;int p = Stop[u].per;int i;for(int i = x ; i < y ; i ++){state[i] += p;if(state[i] > max_size){for(int j = i ; j >= x ; j--)state[j] -= p;return ;}}solve(u + 1,(y - x) * p + money);for(int i = y - 1; i >= x ; i --)state[i] -= p;return ;
}
int main(){while(scanf("%d%d%d",&max_size,&n,&m)){if(!max_size && !n && !m) break;memset(state,0,sizeof(state));ans = 0;for(int i = 0 ; i < m ; i++)scanf("%d%d%d",&Stop[i].x,&Stop[i].y,&Stop[i].per);solve(0,0);printf("%d\n",ans);}return 0 ;
}

这篇关于Transportation-POJ 1040的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---