首页 > 代码库 > zoj 1171 - Sorting the Photos
zoj 1171 - Sorting the Photos
题目:n个叠放在一起的卡片,求使得他们同向的最小翻转次数,每次只能翻转最上面的k个。
分析:数学,贪心。每次翻转必然是不同情况(正,反)交接的地方(否则只会变得更糟);
记交接的地方的个数为m,那么翻转后交接的地方变为m-1或m;
(上面部分两端相同则为m-1,不同则为m)
因此一次翻转最多使得交接点减少1;所以每次翻转最上面的交接点即可。
说明:如果都变成向上或者向下就是dp了(⊙_⊙)。(2011-09-21 11:50)
#include<iostream> #include<cstdlib> using namespace std; char photo[ 100001 ]; int numbe[ 100001 ]; int main() { int n,m;cin >> n; while ( n -- ) { cin >> m; for ( int i = 0 ; i < m ; ++ i ) cin >> photo[ i ]; numbe[ m-1 ] = 0; for ( int i = m-2 ; i >= 0 ; -- i ) if ( photo[ i ] == photo[ i+1 ] ) numbe[ i ] = numbe[ i+1 ]; else { numbe[ i ] = numbe[ i+1 ] + 1; } cout << numbe[ 0 ] << endl; if ( n ) cout << endl; } return 0; }
zoj 1171 - Sorting the Photos
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。