題意
題目我截圖下來了,我大致解釋下,AOJ 0033 Ball。有編號1到10共10個球,從上方丟下去,入口處可以選擇進入左邊或者右邊,最后10個球全部落下去后如果左右兩側都是從小到大的順序,則輸出YES;否則輸出NO。vcD4NCjxwPjxpbWcgYWx0PQ=="這里寫圖片描述" src="http://www.2cto.com/uploadfile/Collfiles/20151213/20151213091427178.jpg" title="\" />
代碼一開始我先測試了一下自己理解的題意是不是對的:
<code class="hljs cpp">#include<iostream>#include<vector>using namespace std;int main() { vector<int>left; vector<int>right; vector<int>all; bool flag = true; int n; cin >> n; if (n == 0) return -1; for (int i = 0; i < n; i++) { for (int j = 0; j < 10; j++) { int temp; cin >> temp; all.push_back(temp); } } for (int i = 0; i < n; i++) { for (int j = 0; j < 10; j++) { if (left.size() > 0) { if (all[10 * i + j] > left[left.size() - 1]) { left.push_back(all[10 * i + j]); } else { if (right.size() > 0) { if (all[10 * i + j] > right[right.size() - 1]) right.push_back(all[10 * i + j]); else flag = false; } else { right.push_back(all[10 * i + j]); } } } else { left.push_back(all[10 * i + j]); } } if (flag) cout << "YES" << endl; else cout << "NO" << endl; flag = true; } return 0;}</int></int></int></vector></iostream></code>后來提交代碼居然錯了,什么鬼!!我用題目中的用例測試是對的啊,還是沒有發現原因在哪……
因為知道題意是要求用DFS,所以改改代碼,思路一樣,再試試:
<code class="hljs cpp">#include<stdio.h>#include<queue>using namespace std;bool flag = true;void solve(queue<int>left, queue<int>right, queue<int>all) { if (all.size() > 0) { if (left.size() > 0) { if (all.front() > left.back()) { left.push(all.front()); all.pop(); solve(left, right, all); } else { if (right.size() > 0) { if (all.front() > right.back()) { right.push(all.front()); all.pop(); solve(left, right, all); } else if(all.size() == 0){ } else { flag = false; } } else { right.push(all.front()); all.pop(); solve(left, right, all); } } } else { left.push(all.front()); all.pop(); solve(left, right, all); } }}int main() { int n; scanf("%d", &n); for (; n > 0; n--) { queue<int>all; queue<int>left; queue<int>right; for (int i = 0; i < 10; i++) { int temp; scanf("%d", &temp); all.push(temp); } solve(left, right, all); if (flag) printf("YES\n"); else printf("NO\n"); } return 0;}</int></int></int></int></int></int></queue></stdio.h></code>這次終于可以了,證明我的思路沒有問題的呀!
找了份代碼過來,變量挺多的:
<code class="hljs cpp">#include<iostream>#include<stack>#include<queue>using namespace std;int main() { stack<int>b, c; int a[10]; bool which[11]; int data[11]; int index; int n, m, A; int i, j; cin >> n; for (i = 0; i<n; cin="" for="" index="0;" j="0;">> m; a[j] = m; data[j + 1] = 0; } b.push(0); c.push(0); while (index >= 0) { A = a[index]; if (b.top() < A && (data[A] != 1 && data[A] != 3)) { b.push(A); data[A] += 1; which[A] = true; } else if (c.top() < A && (data[A] != 2 && data[A] != 3)) { c.push(A); data[A] += 2; which[A] = false; } else { index--; if (index < 0) { break; } else if (which[a[index]]) { b.pop(); } else { c.pop(); } continue; } index++; if (index > 9) { cout << "YES" << endl; break; } } if (index < 0) { cout << "NO" << endl; } }}</n;></int></queue></stack></iostream></code> 这里有更多你想看的
|
- 上一篇:用C++實現一個Log系統 -電腦資料
- 下一篇:返回列表