1666: [Usaco2006 Oct]Another Cow Number Game 奶牛的数字游戏
如果N是奇数，就把它乘以3后再加1。如果N是偶数，那么这个数就会被除以2。
当N的值等于1时停止。问变换的次数。
1、数据太弱，直接模拟0s可过：其实还需特判1+大数据开LL
处理的数据可能远大于n，无法估计数据可能达到的大小时一定要开LL
2、记忆化搜索？这道题会慢很多
注意到1000W一下的数会被访问很多次，所以记录1000W以下的。
#include <iostream>
using namespace std;
int a[11111111];
int gao(long long x)
{
if(x == 1) return 1;
if(x < 10000000 && a[x]) return a[x];
int tmp;
if(x % 2 == 0)
tmp = gao(x / 2) + 1;
else
tmp = gao(x * 3 + 1) + 1;
if(x < 10000000) a[x] = tmp;
return tmp;
}
int main()
{
int n;
cin >> n;
cout << gao(n) - 1<< endl;
return 0;
}
3、著名的“角谷猜想”
这样一直算下去，最后数字会在一个循环圈里循环，这个循环圈是（4→2→1→4）。
即经过有限步后，一定可以得到1
扩展：
任举一个正整数n，如果n能被a整除，就将它变为n/a,如果除后不能再整除，则将它乘b加c（即bn+c）。不断重复这样的运算，经过有限步后，一定可以得到d吗？
1579: [Usaco2009 Feb]Revamping Trails 道路升级
求无向带权图1-n最短路,其中可选择k条路径使其权值为0.
1690: [Usaco2007 Dec]奶牛的旅行
有向图中,点和边均有权值,要求找出一个环,使环内(Σ边权)/(点权)最大。不考虑自环。
1708: [Usaco2007 Oct]Money奶牛的硬币
多重背包dp.
1782: [Usaco2010 Feb]slowdown 慢慢游
1711: [Usaco2007 Open]Dining吃饭
经典网络流
1725: [Usaco2006 Nov]Corn Fields牧场的安排
经典状压dp
1592: [Usaco2008 Feb]Making the Grade 路面修整
将一个序列A更改为不上升/不下降序列B的最小费用,费用定义为 |A_1 - B_1| + |A_2 - B_2| + ... + |A_N - B_N|
经典dp
1715: [Usaco2006 Dec]Wormholes 虫洞
评论 (0)
