三角形

题意是：给你n个背包，每个背包装了mi个物品，每个背包选一个，要求出选出物品价值前k小 的不同方案种数，很容易联想到背包dp。
那么怎么做呢？我们可以考虑dp[i][j]表示前i个背包选出来价值和为j的方案个数，则有

dp[i][k]+=dp[i-1][k-a[i][j]];

这个是状态转移方程，具体看代码
CODE

#include<bits/stdc++.h>
using namespace std;

int n,k;
int dp[105][10010],a[105][110];  //dp[i][j]代表前i个宝盒我选了价值为j的方案数量
void solve()
{
    cin>>n>>k;
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        int t;
        cin>>t;
        for(int j=1;j<=t;j++){
            cin>>a[i][j];
            for(int k=10000;k>=a[i][j];k--)
            {
                dp[i][k]+=dp[i-1][k-a[i][j]];
            }
        }
    }

    int ans=0;
    for(int i=0;i<=10000;i++){
        if(k>dp[n][i]) ans+=(dp[n][i])*i,k-=dp[n][i];
        else{
            ans+=k*i;
            break;
        }
    }
    cout<<ans<<endl;
}
int  main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}