正題

---

題目大意

第ii行有n?i+1n?i+1個格子，每一行要求從左到右畫#，要求下面哪行的#數不能超過前一行。要求第一行必須有#，求畫的方案數。

---

解題思路

首先一定要高精度，然后就是dp了：
這個dp比較慢是O(n3)O(n3)的
用f[i][j]f[i][j]表示第i行放j個的方案數，然后枚舉一個k表示上一行選k個就好了，最后把f都統計一遍。

---

代碼

#include<cstdio> using namespace std; int n,s,f[101][101]; int a[10001][26]; void add(int n1,int n2)//高精度 {int z=0;for (int i=1;i<=25;i++){a[n1][i]=a[n1][i]+a[n2][i]+z;z=a[n1][i]/1e8;a[n1][i]%=(int)1e8;} } void write(int x)//輸出 {int w=25;while (a[x][w]==0) w--;printf("%d",a[x][w]);w--;for (;w>=1;w--){if (a[x][w]/(int)1e7==0) printf("0");//壓位if (a[x][w]/(int)1e6==0) printf("0");if (a[x][w]/(int)1e5==0) printf("0");if (a[x][w]/(int)1e4==0) printf("0");if (a[x][w]/(int)1e3==0) printf("0");if (a[x][w]/(int)1e2==0) printf("0");printf("%d",a[x][w]);} } int main() {//freopen("diagrams.in","r",stdin);//freopen("diagrams.out","w",stdout);scanf("%d",&n);for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)f[i][j]=(i-1)*n+j;//分配數組for (int i=1;i<=n;i++){a[f[1][i]][1]=1;//初始化add(s,f[1][i]);//累計}for (int i=2;i<=n;i++){for (int j=1;j<=n-i+1;j++){for (int k=j;k<=n;k++){add(f[i][j],f[i-1][k]);//動態轉移}add(s,f[i][j]);//累計}}write(s); }

總結

以上是生活随笔為你收集整理的【2018.5.12】模拟赛之四-ssl2416 条形图【高精度,dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。