Maybe you have to make a larger array to put the answer. thank you very much,, I've been stuck in this problem for weeks because of this. 3 4 1 100 1000 0 1 1 1000 0 100 0 1000 100 //answer 1 1 2 2 1 1 1000000000 //answer 1 5 6 525 0 171 0 872 673 0 843 0 0 0 0 0 277 0 202 0 0 0 0 733 957 65 96 637 566 0 0 0 441 //answer: 4 4 5 5 5 5 10 1 10 10 10 1 1 10 10 10 1 10 1 1 1 1 1 1 10 1 10 10 10 10 1 //answer: 2 2 1 1 1 1 1 10 100 90 80 70 60 50 40 30 20 10 //answer: 10 5 6 1 0 1 1 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 //answer: 2 2 3 3 3 2 2 3 2 3 1 1 1 1 3 //answer: 2 2 1 1 3 1 1 1 1 //answer: 1 1 1 You 3rd and 6th test cases are wrong. The fee should be positive. I solved this problem with algo of Dijkstra. Edge : (i,j)->(i+1,j), (i-1, j), (i, j+1) with weight of a[i]j]; Edited by author 19.02.2022 12:12 Why I get WA?! Edited by author 19.02.2022 12:12 Edited by author 19.02.2022 12:13 There is no reason to use long arithmetic.. Read the hint. Though may be you store something amazing to solve the task in more effecient way... In any case, the problem is solvable without long arithmetic WTF REALLY IT HELPS ME!!! THANKS YOU. Я ТУПО СИДЕЛ И НИЧЕГО НЕ ПОНИМАЛ ПОЧЕМУ НЕ РАБОТАЕТ, ЛОНГИ ПОМОГЛИ!! только я не понял почему вообще инт не залетел) I am using DP, it works for all TC on discussion. what could be wrong? My code fails with WA#1 although it passes every test cases that I've found in comments. Any hints? Need help. Stuck for serval weeks! What is wa3 like? What is wa6 like? i also got wa on 5 and then found out i considered room and floor both can be at most 100. but problem says floor is 100 and room can be at most 500. I used dijkstra to do in O(mnlog(mn))? Whats your approach? I used dynamic programming to solve the question. dp[floor][room][lastStep] indicates the best way to reach top when we are on floor, room and the last step is know. Each state of dp is solved in constant time as we have to do only 2 computations at each step. But my approach runs very very slow. Two dimensions are enough DP can solve this problem in O(MN). If you have WA15 use for dp and for fees long long, because not optimal answer for official, which can be before program find optimal answer, may be more then 10^9. Может, я чего и не понимаю, но почему подобный код получает TL#1? #include <stdio.h> #include <stdlib.h> #include <string.h> #define inf 2100000000 int a[2][510],res[2][510]; char fy[110][510]; int n,m,min,i1,i2; void Rec(int i, int j) { if (i > 1) { if (fy[i][j] == j) Rec(i-1,j); else Rec(i,fy[i][j]); }; printf("%d\n",j); }; int main(void) { int i,j; scanf("%d%d",&m,&n);
for (j = 1; j <= n; j++) scanf("%d",&a[1][j]); for (i = 1; i <= n; i++) res[1][i] = a[1][i]; for (i = 2; i <= m; i++) for (j = 1; j <= n; j++) res[i][j] = inf; for (i = 1; i < m; i++) { i1 = i%2; i2 = (i+1)%2; for (j = 1; j <= n; j++) scanf("%d",&a[i2][j]); for (j = 1; j <= n; j++) { res[i2][j] = res[i1][j] + a[i2][j]; fy[i+1][j] = j; }; for (j = 2; j <= n; j++) if (res[i2][j] > res[i2][j-1] + a[i2][j]) { res[i2][j] = res[i2][j-1] + a[i2][j]; fy[i+1][j] = j-1; }; for (j = n-1; j >= 1; j--) if (res[i2][j] > res[i2][j+1] + a[i2][j]) { res[i2][j] = res[i+1][j+1] + a[i2][j]; fy[i+1][j] = j+1; }; }; min = inf; for (i = 1; i <= n; i++) if (res[m%2][i] < min) { min = res[m%2][i]; i1 = i; }; Rec(m,i1); return 0; }; Почему scanf и printf. Ты используешь cin и cout. (Because of scanf and printf. It's better to use cin and cout) I don't know why my program has WA#1. My computer gives correct answer. Please help me, maybe you had the same problem. If you have written your solution in C++ and you use scanf and printf, it would be better to use cin and cout. I don't know why I get WA on test 4! Can there be a negative number? This is my code: #include<iostream> #include<cmath> using namespace std; long long dyn[110][510] , a[110][510] , big, sum[110][510] , p[110][510][2] , o , m, n; int main(){ cin>>m>>n; for(int i=0;i<m;i++) for(int j=0;j<n;j++) cin>>a[i][j]; for(int i=0;i<m;i++) { sum[i][0]=a[i][0]; dyn[i][0]=100000000000000000; for(int j=1;j<n;j++) { sum[i][j]=sum[i][j-1]+a[i][j]; dyn[i][j]=100000000000000000; } } if((m==1)&&(n==1)) { cout<<1<<endl; return 0; } dyn[m-1][0]=a[m-1][0]; for(int i=1;i<n;i++) { dyn[m-1][i]=a[m-1][i]; } for(int i=m-2;i>=0;i--) { for(int j=n-1;j>=0;j--) { for(int k=0;k<n;k++) { if(j>k) { if(dyn[i+1][k]+sum[i][j]-sum[i][k-1]<dyn[i][j]) { dyn[i][j]=dyn[i+1][k]+sum[i][j]-sum[i][k-1]; p[i][j][0]=j; p[i][j][1]=k; } } else { if(dyn[i+1][k]+sum[i][k]-sum[i][j-1]<dyn[i][j]) { dyn[i][j]=dyn[i+1][k]+sum[i][k]-sum[i][j-1]; p[i][j][0]=j; p[i][j][1]=k; } } } } } big=dyn[0][0]; o=0; for(int i=1;i<n;i++) { if(dyn[0][i]<big) { big=dyn[0][i]; o=i; } } cout<<o+1; for(int i=1;i<m-1;i++) { if(p[i][o][0]<=p[i][o][1]) { for(int j=p[i][o][0];j<=p[i][o][1];j++) cout<<" "<<j+1; } else { for(int j=p[i][o][0];j>=p[i][o][1];j--) cout<<" "<<j+1; } o=p[i][o][1]; } cout<<" "<<o+1<<endl; return 0; } No there can't be. My ac code. [code deleted] Edited by moderator 19.11.2019 23:27 Seems like your AC code fails at test: 5 5 10 1 10 10 10 1 1 10 10 10 1 10 1 1 1 1 1 1 10 1 10 10 10 10 1 I'm sorry. I should be more careful while reading the problem statement. The correct answer here is 2 2 1 1 1 1. Not 2 2 1 1 1 2 3 3 4 5 5 5. This test helped me to get AC, though I think it's good only against my solution: 3 4 1 100 1000 0 1 1 1000 0 100 0 1000 100 //answer 1 1 2 2 it helps me a lot! appreciate you in chinese :谢谢你 The fee is a POSITIVE integer. I don't understand what the output means? thanks for help! OUTPUT: 3 3 2 1 1 MOVE 1: 1st floor [3]rd room MOVE 2: 2nd floor [3]rd room MOVE 3: 2nd floor [2]nd room MOVE 4: 2nd floor [1]st room MOVE 5: 3rd floor [1]st room More Detailed: Let out[] be the output array. If out[i] == out[i+1] then it means that you go one floor up, as there is no point in revisiting the same official. Otherwise you go to one of the neighboring rooms. If out[i] + 1 == out[i+1] then you go to the right neighboring room. Else if out[i] - 1 == out[i+1] then you go to the left neighboring room. Hope it helped you. And hope that my C-style like syntax didn't make it hard to understand :) Edited by author 25.08.2013 14:31 My code: What's wrong??? #include <algorithm> #include <vector> #include <utility> #include <stdio.h> #define ARRAY_SIZEOF(a) (sizeof(a) / sizeof(a[0])) #define INF 0x7fffffff using namespace std; typedef long long int lli; int M, N; int C[100][500]; int T[101][500]; int m1[500]; int m2[500]; int path[500*500]; int main() { #ifndef ONLINE_JUDGE freopen("in", "r", stdin); #endif int i, j, k; scanf("%d%d", &M, &N); for (i = 0; i < M; i++) { for (j = 0; j < N; j++) { scanf("%d", &C[i][j]); C[i][j]++; T[i+1][j] = INF; } } for (i = 1; i <= M; i++) { m1[0] = T[i-1][0] + C[i-1][0]; for (j = 1; j < N; j++) { m1[j] = min(m1[j-1], T[i-1][j]) + C[i-1][j]; } m2[N-1] = T[i-1][N-1] + C[i-1][N-1]; for (j = N-1; j-- > 0; ) { m2[j] = min(m2[j+1], T[i-1][j]) + C[i-1][j]; } for (j = 0; j < N; j++) { T[i][j] = min(m1[j], m2[j]); } } int jmin = 0; for (j = 1; j < N; j++) { if (T[M][j] < T[M][jmin]) { jmin = j; } } i = M; j = jmin; k = 0; do { path[k++] = j + 1; int m = T[i-1][j]; jmin = j; if (j-1 >= 0 && T[i][j-1] < m) { jmin = j-1; m = T[i][jmin]; } if (j+1 < N && T[i][j+1] < m) { jmin = j+1; m = T[i][jmin]; } if (m == T[i-1][j]) i--; else j = jmin; } while (i); for (i = 0; i < k; i++) { printf("%d ", path[k-1-i]); } printf("\n"); return 0; } Can anyone help me ? I have WA16 and i don't know what is wrong with my code . UPD : Test 16 is a big test . I replaced in one place int with long long and i got AC. Good Luck :) ! Edited by author 25.05.2013 14:23 Think about this case If you use DP 2 2 1 1 0 0 when considering the elem 0 at [1, 0] , you can find the way from [0, 1] -> [1, 0] and [0, 1] -> [1, 1] -> [1, 0] have the same sum(both are 1), how to handle this situation ? I handle this by giving the way from `ABOVE` higher priority, or else when printing the path to the answer, you wil get [1, 0] <- [1, 1] <- [1, 0] <- [1, 1] ....... which is WA. and another thing to notice is you may need long long to hold. hope it helps :) |
|