首页 > 代码库 > HDU 4175 Class Schedule (暴力+一点dp)
HDU 4175 Class Schedule (暴力+一点dp)
HDU 4175
题意:有C座楼,每座楼有T个教室。一个人须要訪问C个教室。每座楼仅仅能訪问一个教室。
訪问教室须要消耗能量,从x点走到y点须要消耗abs(x-y)的能量,最后要走到目的点L,问最后走到目的点L须要消耗的最少能量。
思路:读清题意,用getchar()的方式去读。。
此外英文阅读水平比較拙计,亟待提升,以后不能再直接用有道翻译来做题了。
直接暴力枚举。用dp[i][j]表示class = i , classroom = j的所需最小能量。
dp[i][j] = dp[i-1][k] + abs(e[i-1][k].pos - e[i][j].pos) + e[i][j].cost;直接看代码吧:)
code:
/* * @author Novicer * language : C++/C */ #include<iostream> #include<sstream> #include<fstream> #include<vector> #include<list> #include<deque> #include<queue> #include<stack> #include<map> #include<set> #include<bitset> #include<algorithm> #include<cstdio> #include<cstdlib> #include<cstring> #include<cctype> #include<cmath> #include<ctime> #include<iomanip> #define inf 20000000 using namespace std; const double eps(1e-8); typedef long long lint; struct cl{ int pos; int cost; }; cl e[30][1005]; int dp[30][1005];//dp[i][j]表示class = i , classroom = j的所需最小能量 int main(){ // freopen("input.txt","r",stdin); int kase; cin >> kase; while(kase--){ // memset(e,0,sizeof(e)); memset(dp,0,sizeof(dp)); int c,t,l; cin >> c >> t >> l; for(int i = 1 ; i <= c ; i++){ for(int j = 1 ; j <= t ; j++){ scanf("%d%d",&e[i][j].pos,&e[i][j].cost); } } for(int i = 1 ; i <= c ; i++){ for(int j = 1 ; j <= t ; j++){ int tmp = inf; for(int k = 1 ; k <= t ; k++){ dp[i][j] = dp[i-1][k] + abs(e[i-1][k].pos - e[i][j].pos) + e[i][j].cost; tmp = min(dp[i][j] , tmp); } dp[i][j] = tmp; // cout << dp[i][j] << endl; } } int ans = inf; for(int i = 1 ; i <= t ; i++){ int value = http://www.mamicode.com/dp[c][i] + abs(l - e[c][i].pos);>
HDU 4175 Class Schedule (暴力+一点dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。