hdu1396(数三角形)的递推公式怎么推出来的hdu1396的递推公式怎么推出来的a[i] = a[i-1]+i*(i+1)/2;

来源:学生作业帮助网 编辑:作业帮 时间:2024/11/27 02:49:49
hdu1396(数三角形)的递推公式怎么推出来的hdu1396的递推公式怎么推出来的a[i] = a[i-1]+i*(i+1)/2;
xTmOP+ 7Z|1K(&0,٧dFԩo@ɶB73)貹/rۛ<<9@2iϏb]Wucm !AR|yhÿbgk1 ɯބ_~HFC<19K%R(KHb|%1A yf ExPXR%0+'H^/pE%>*%D|Ra1C7i ZwZNQ+ȄrtvUws"tTrs:awY0Zm\uPP FCi`B#qʰ3V&gʺ&ӱ{rM(޵'HVr^{^K!SI1

hdu1396(数三角形)的递推公式怎么推出来的hdu1396的递推公式怎么推出来的a[i] = a[i-1]+i*(i+1)/2;
hdu1396(数三角形)的递推公式怎么推出来的
hdu1396的递推公式怎么推出来的
a[i] = a[i-1]+i*(i+1)/2;

hdu1396(数三角形)的递推公式怎么推出来的hdu1396的递推公式怎么推出来的a[i] = a[i-1]+i*(i+1)/2;
那个公式应该不是算总共的三角形数目的


应该是算多少个正立的三角形的数目





假设红色三角形是n-1的边长
那么黄色+红色的大三角形的边长是n


假设如果一个三角形全部由红色构成,那么这个三角形已经在a[n-1]中被计算了
所以我们只需要计算至少包含一个黄色块的三角形的个数


我们可以发现,这些包含黄色块的三角形,其中一条边必定在大三角的底边上,而且和大三角形底边的子线段成一一对应关系


底边的子线段的个数是(n+1)个点里面任取2个不同点的取法的个数
所以是(n+1) * n / 2


所以a[n] = a[n-1] + (n+1) * n / 2