准备期末之前做完
人一我百！人十我万！永不放弃~~~怀着自信的心，去追逐梦想

方法，求概率正着推，求期望倒着推

单独写：
分析: 倒着推就行
code： 
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;
const int maxn = 1004;
double dp[maxn][maxn];
int main()
{
    int n,s;
    while(~scanf("%d%d",&n,&s))
    {
        dp[n][s]=0;
        for(int i=n;i>=0;i--)
          for(int j=s;j>=0;j--)
          {
              if(i==n&&j==s)continue;
              dp[i][j]=(i*(s-j)*dp[i][j+1]+(n-i)*j*dp[i+1][j]+(n-i)*(s-j)*dp[i+1][j+1]+n*s)/(n*s-i*j);
          }
          printf("%.4f\n",dp[0][0]);
    }
    return 0;
}
分析 ：感觉比bin神写的好看
code： 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
double dp[maxn];
int go[maxn];
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        if(n==0&&m==0) break;
        int x,y;
        for(int i=0;i<=n+6;i++) go[i]=0,dp[i]=0.0;
        for(int i=1;i<=m;i++) {
            scanf("%d%d",&x,&y);
            go[x]=y;
        }
        for(int i=n+5;i>=0;i--)
            if(!go[i]) {
                if(i<n) {
                    for(int j=1;j<=6;j++) dp[i]+=dp[i+j]/6;
                    dp[i]++;
                }
                else continue;
            }
            else {
                if(i<n) dp[i]=dp[go[i]];
                else continue;
            }
        printf("%.4f\n",dp[0]);
    }
    return 0;
}
这题好难.......还没想好
code : 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 5;
double e[maxn];
vector<int> v[maxn];
bool dfs(int )
{

    return true;
}
int main()
{
    int t,kase=0;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<n;i++) {
            scanf("%d%d",&x,&y);
            v[x].push_back(y);
            v[y].push_back(x);
        }
        for(int i=1;i<=n;i++) 
        printf("Case #%d: ",++kase);
        printf("impossible\n");
        printf()
    }
    return 0;
}


分析: 需考虑 a[ i ][ j ] == 1 的坑点，容易wa
code: 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1004;
double a[maxn][maxn],b[maxn][maxn],c[maxn][maxn],dp[maxn][maxn];
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
            scanf("%lf%lf%lf",&a[i][j],&b[i][j],&c[i][j]);
        dp[n][m]=0;
        for(int i=n;i>=1;i--) for(int j=m;j>=1;j--)
            if((i==n&&j==m)||a[i][j]==1.0) continue;//在移动到该点之后就再也动不了了
            else dp[i][j]=(dp[i][j+1]*b[i][j]+dp[i+1][j]*c[i][j]+2)/(1-a[i][j]);
        printf("%.3f\n",dp[1][1]);
    }
    return 0;
}
分析: 水题，推式子 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int n,m;
    double p=1.0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) p=p*(1.0*(n-1)/n);
    printf("%.10lf",n-p*n);
    return 0;
}
分析 ：记忆化搜索，这一题值得学习，我经常想不到去写记搜
code : 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
int n,f,c[102];
double t[102],dp[maxn];
double cal(int x)
{
    if(dp[x]) return dp[x];
    for(int i=1;i<=n;i++)
        if(x>c[i]) dp[x]+=t[i]*1.0/n;
        else dp[x]+=(1+cal(x+c[i]))/n;
    return dp[x];
}
int main()
{
    while(~scanf("%d%d",&n,&f))
    {
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++) {
            scanf("%d",&c[i]);
            t[i]=int((1.0+1.0*sqrt(5))/2*1.0*c[i]*c[i]);
        }
        printf("%.3f\n",cal(f));
    }
    return 0;
}

高斯消元: