UVA 10603 Fill(准确代码虽然很搓,网上许多代码都不能AC)
UVA 10603 Fill(正确代码虽然很搓,网上许多代码都不能AC)
题目链接:click here~
此题我估计是加强过数据,在我纠结了很久的时候我交了好几份网上的代码不是WA就是TLE。在我很迷茫的时候我又交了一份,AC了(虽然我用随机数据找到了他代码一个不能过的数据)。
给了我信心,然后我拿他的代码用随机数跟我的代码进行测试,再用FC找不同。。发现了一个致命的错误,一般来说,BFS或者DFS都是需要有一个vis数组或者哈希来判重,但是此题判重是有很大问题的,同样对于3个水杯的状态,在3步下也许流量是50,然后这个状态被标记,5步的时候又出现了这个状态(可以理解为另一个分支),但是流量却是35,如果用个二维数组判重(没有必要用三维的,因为和是一样的,二维就可以了),那么这个状态的流量就不会更新,题目的意思却是说要用最小的流量去到达这个状态,不管是得到最终的目标还是比目标小最近目标的状态。
所以我感觉这题的标准解法应该不是 bfs,因为可以说是算暴力了,每一次的状态(如果流量比上一个到这个状态的流量少)都需要更新,不断更新直到最后。在uva toolkit上此题的思路是dp或dijkstra。这2样还没怎么搞不太会,建图也想不到想法,感觉就算建了还是搜索的东西啊
虽然A了,但是感觉不爽啊。另外我找的那个A了的代码没过的数据是:33 12 113 6
他的结论是 174 6,我的结论是171 6,在uva toolkit上也是我的答案,但是我觉得他的思路应该是正确的,没细看。。实在是太长了。
如果有想法的欢迎留言。
代码供参考:
#include<cstdio> #include<ctype.h> #include<algorithm> #include<iostream> #include<cstring> #include<vector> #include<stack> #include<cmath> #include<queue> #include<set> using namespace std; #define ll long long #define NMAX 20000 typedef int state[3]; state st[NMAX],a; int pour[NMAX]; int record[205]; int target; int vis[205][205],vispour[205][205]; int try_to_insert(int x,int tpour) { state &k = st[x]; if(vis[k[0]][k[1]] != 1 || vispour[k[0]][k[1]] > tpour) { vis[k[0]][k[1]] = 1; vispour[k[0]][k[1]] = tpour; return 1; } return 0; } int main() { // freopen("input.txt","r",stdin); // freopen("o.txt","w",stdout); int i,j,t,ans; scanf("%d",&t); while(t--) { memset(record,0,sizeof(record)); memset(vis,0,sizeof(vis)); memset(vispour,0,sizeof(vis)); scanf("%d%d%d%d",&a[0],&a[1],&a[2],&target); st[1][0] = st[1][1] = 0; st[1][2] = a[2]; memset(pour,0,sizeof(pour)); record[a[2]] = 1; int front = 1,rear = 2; vis[0][0] = 1; bool flag = false; while(front < rear) { for(i = 0; i < 3; i++) if(record[st[front][i]] == 0 || pour[record[st[front][i]]] > pour[front]) record[st[front][i]] = front; for(i = 0; i < 3; i++) if(st[front][i] == target) { if(flag) ans = pour[ans] > pour[front]?front:ans; else ans = front; flag = true; break; } for(i = 0; i < 3; i++) { state &w = st[front]; if(w[i] != 0) { for(j = 0; j < 3; j++) { if(i == j || (i != j && w[j] == a[j])) continue; state &temp = st[rear]; memcpy(temp,w,sizeof(w)); int pp; if(w[i] + w[j] > a[j]) { pp = a[j] - w[j]; temp[i] = w[i] - pp; temp[j] = a[j]; } else { pp = w[i]; temp[i] = 0; temp[j] = w[j] + pp; } int tpour; tpour = pour[front] + pp; if(try_to_insert(rear,tpour)) { pour[rear] = tpour; rear++; } } } } front++; } if(record[target] == 0) { for(i = target; record[i] == 0; i--); printf("%d %d\n",pour[record[i]],i); } else printf("%d %d\n",pour[ans],target); } return 0; }