首页 > 代码库 > 【动态规划】【记忆化搜索】【搜索】CODEVS 1262 不要把球传我 2012年CCC加拿大高中生信息学奥赛
【动态规划】【记忆化搜索】【搜索】CODEVS 1262 不要把球传我 2012年CCC加拿大高中生信息学奥赛
可以暴力递归求解，应该不会TLE，但是我们考虑记忆化优化。
设f(i,j)表示第i个数为j时的方案数。
f(i,j)=f(1,j-1)+f(2,j-1)+……+f(i-1,j-1) (4>=j>=1)，从f(n,4)开始递归求解就行。
但是考虑到状态最多只有n*4种，所以记忆化掉吧。
初始化：f(i,1)=1 (1<=i<=n-3)
1 #include<cstdio> 2 using namespace std; 3 int n; 4 long long memory[5][101]; 5 long long f(int cur,int now) 6 { 7 if(now==0||cur<now) return 0; 8 if(memory[now][cur]) return memory[now][cur]; 9 long long res=0;10 for(int i=1;i<cur;i++) res+=f(i,now-1);11 return memory[now][cur]=res;12 }13 int main()14 {15 scanf("%d",&n);16 for(int i=1;i<=n-3;i++) memory[1][i]=1;17 printf("%lld\n",f(n,4));18 return 0;19 }
【动态规划】【记忆化搜索】【搜索】CODEVS 1262 不要把球传我 2012年CCC加拿大高中生信息学奥赛
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。