题目在此 http://poj.org/problem?id=2698
题目大意是给定一串要播放的DVD顺序，但是DVD drives数量有限，每次将DVD放入DVD drive都记为一次插入，问把DVD按照给定的顺序播放得到的最小插入值是多少
本题涉及一个贪心算法，有个极为高端大气的名字：最佳置换算法，或者称之为(操作系统的)最优页面替换算法，以下博客是对该算法的模拟过程，已经写得十分详细
http://blog.csdn.net/luoweifu/article/details/8498027
该算法大意是给定DVD播放顺序数列，当DVD drives里面都有DVD,且自己要放的DVD并不在这些已放入DVD drive的DVD之列时,遍历该DVD后面要放的DVD(最早出现),最后出现的被新DVD取代(再也没有出现的记为inf)，eg.1 2 3 4 1 3 3 1(two DVD drives)，放入1，放入2，drive已满，2为inf被3取代，4后面的的1和3，1先出现，则，把3替换，而之后1和3都在DVD drive里面，则不用插入
代码如下： #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; const int inf = 0x7fffffff; int n, m, ans, op[105], pos[1000005]; bool exist[1000005]; int drive[15], temp[15]; //n为DVD drives数量 //m为操作数 int find(int opr) { int res = -1, opaa; for(int i = 1; i <= n; i++) { if(pos[op[drive[i]]] < opr) temp[i] = inf; else { for(int j = opr + 1; j <= m; j++) { if(op[drive[i]] == op[j]) { temp[i] = j; break; } } } } for(int i = 1; i <= n; i++) { if(res < temp[i]) { res = temp[i]; opaa = i; if(res == inf) break; } } return opaa; } void solve(int opr, int k)//opr为操作数， k为正在使用的DVD drives编号 { if(opr > m) return; if(k > n) { if(exist[op[opr]]) solve(opr + 1, k); else { ans++; int opaa = find(opr); exist[op[drive[opaa]]] = false; exist[op[opr]] = true; drive[opaa] = opr; solve(opr + 1, k); } } else { if(exist[op[opr]]) solve(opr + 1, k); else { exist[op[opr]] = true; ans++; drive[k] = opr; solve(opr + 1, k + 1); } } } int main() { int t; scanf("%d", &t); while(t--) { memset(exist, false, sizeof(exist)); memset(drive, 0, sizeof(drive)); memset(temp, 0, sizeof(temp)); memset(pos, 0, sizeof(pos)); memset(op, 0, sizeof(op)); ans = 0; scanf("%d%d", &n, &m); for(int i = 1; i <= m; i++) { scanf("%d", &op[i]); pos[op[i]] = max(pos[op[i]], i); } solve(1, 1); printf("%d\n", ans); } return 0; }