本文主要是介绍hd 1988 Flipping Burned Pancakes，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
做练习赛时,没来的及看.后来看的时候发现可以用bfs+递归求解,写好后TLE,后来又改成了dfs,一样TLE.后来又问了WY,直接构造就可以了,方法是先排大的,再排小的.
/*
方法:直接构造,先排大的,再排小的...
*/
#include < iostream >
#include < queue >
using namespace std;
int a[ 32 ], n;
void change( int t)
{
int i;
for (i=1; i<=t; ++i)
{
a[i] *= -1;
}
for (i=1; i<=t/2; ++i)
{
int tt = a[i];
a[i] = a[t-i+1];
a[t-i+1] = tt;
}
}
int main()
{
int i, j, index = 1;
int N;
char c;
queue<int> mq;
scanf("%d", &N);
while (N--)
{
scanf("%d", &n);
for (i=1; i<=n; ++i)
{
scanf(" %c%d", &c, &a[i]);
if(c == '-')
a[i] *= -1;
}
for (i=n; i>=1; --i)
{
if(a[i] != i)
{
while (1)
{
for (j=1; j<=n; ++j)
{
if(abs(a[j]) == i)
break;
}
if(j==1 && a[j]==-i)
{
change(i);
mq.push(i);
break;
}
else
{
change(j);
mq.push(j);
}
}
}
}
printf("%d %d", index++, mq.size());
while (!mq.empty())
{
printf(" %d", mq.front());
mq.pop();
}
printf(" ");
}
return 0;
}
/*
方法:直接构造,先排大的,再排小的...*/ #include < iostream > #include < queue > using namespace std; int a[ 32 ], n; void change( int t) { int i; for (i=1; i<=t; ++i) {
a[i] *= -1; } for (i=1; i<=t/2; ++i) { int tt = a[i]; a[i] = a[t-i+1]; a[t-i+1] = tt; }} int main() { int i, j, index = 1; int N; char c; queue<int> mq; scanf("%d", &N); while (N--) { scanf("%d", &n); for (i=1; i<=n; ++i) { scanf(" %c%d", &c, &a[i]); if(c == '-') a[i] *= -1; } for (i=n; i>=1; --i) { if(a[i] != i) { while (1) { for (j=1; j<=n; ++j) { if(abs(a[j]) == i) break; } if(j==1 && a[j]==-i) { change(i); mq.push(i); break; } else { change(j); mq.push(j); } } } } printf("%d %d", index++, mq.size()); while (!mq.empty()) { printf(" %d", mq.front()); mq.pop(); } printf(" "); } return 0;} 这篇关于hd 1988 Flipping Burned Pancakes的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
