1、给定一个$n$个顶点$n$个边的图，边是$(i,a_{i})$，顶点编号$[0,n-1]$。增加一个顶点$n$,现在选出一个顶点集$M$,对于任意的在$M$中 的顶点$x$，去掉边$(x,a_{x})$，增加边$(x,n)$。最后使得顶点0和1相连。有多少种$M$?
思路：设从0开始可以遍历的顶点集合为$A$,从1可以遍历的顶点集合为$B$，$C=Aigcap B$。令$A^{'}=A-C,B^{'}=B-C$。那么有下面的情况：
（1）在$C$中选择一些点（至少一个），从$A^{'},B^{'}$中任意选点；
（2）在$C$中不选择点，从$A^{'},B^{'}$中任意选点（不能为空）；
（3）假设$C$不为空，那么可以不从$A^{'},B^{'},C$中选择。
对于不在$A^{'},B^{'},C$中的点都是随便选。
#include <stdio.h>
#include <string>
#include <stack>
#include <vector>
#include <string.h>
#include <algorithm>
#include <assert.h>
using namespace std;
const int N=55;
#define B(x) (1ll<<(x))
class Sunnygraphs {
public:
long long count(vector<int> a)
{
int n=(int)a.size();
vector<int> mask(n);
for(int i=0;mask[i]<1;i=a[i]) mask[i]|=1;
for(int i=1;mask[i]<2;i=a[i]) mask[i]|=2;
int c[4]={0,0,0,0};
for(int i=0;i<n;++i) ++c[mask[i]];
long long ans=0;
ans+=(B(c[3])-1)*B(c[1])*B(c[2]);
ans+=(B(c[1])-1)*(B(c[2])-1);
if(c[3]) ++ans;
ans<<=c[0];
return ans;
}
};
2、给定$n$组数字$(a_{i},b_{i})$，$n$为偶数。现在重新排列这$n$组数字，得到新的$(A_{i},B_{i})$，使得下面的值最大：
$ans=sum_{i=1}^{frac{n}{2}}(B_{i}sum_{j=1}^{i}A_{j})+sum_{i=frac{n}{2}+1}^{n}(B_{i}(X+sum_{j=1}^{i}A_{j}))$
其中$2leq nleq 50,1leq a_{i}leq100000,1leq b_{i}leq10,0leq Xleq 100000$
思路：现在考虑考虑最后分在前一半的两组$(A_{i},B_{i}),(A_{j},B_{j})$，若$i$在前优于$j$在前，那么$A_{i}B_{i}+(A_{i}+A_{j})B_{j}geq A_{j}B_{j}+(A_{i}+A_{j})B_{i}$，即$A_{i}B_{j}geq A_{j}B_{i}$。
由于$b_{i}$较小，现在枚举最后后一半的数字的所有的$A_{i}$之和$S$，那么现在对于一个数对，可以直接枚举它在前一半还是后一半（现在不管它在前一半还是后一半都可以直接计算对答案的贡献），这样可以进行动态规划。令$f[i][j][k]$表示现在已经考虑了$i$个数字，后一半数字的个数为$j$，后一半数字的$B$之和为$k$能得到的最大值，答案为$f[n][n/2][S]$。
#include <stdio.h>
#include <string>
#include <stack>
#include <vector>
#include <string.h>
#include <algorithm>
#include <assert.h>
using namespace std;
int cmp(pair<int,int> a,pair<int,int> b)
{
return a.first*b.second<b.first*a.second;
}
int f[55][33][505];
int A[55],B[55];
void up(int &x,int y)
{
if(x<y) x=y;
}
int n;
void DP(const int NextSumB,const int X)
{
memset(f,-1,sizeof(f));
f[0][0][0]=0;
int pre=0;
for(int i=1;i<=n;++i)
{
pre+=B[i];
for(int j=0;j<=n/2;++j) for(int k=0;k<=pre;++k)
{
if(f[i-1][j][k]>=0)
{
up(f[i][j][k],f[i-1][j][k]+A[i]*(pre-k)+A[i]*NextSumB);
up(f[i][j+1][k+B[i]],f[i-1][j][k]+A[i]*B[i]+A[i]*k+X*B[i]);
}
}
}
}
class Moneymanager {
public:
int getbest(vector<int> a,vector <int> b,int X) {
vector<pair<int,int> > p;
n=(int)a.size();
int sum=0;
for(int i=0;i<n;++i) {
p.push_back(make_pair(a[i],b[i]));
sum+=b[i];
}
sort(p.begin(),p.end(),cmp);
for(int i=1;i<=n;++i)
{
A[i]=p[i-1].first;
B[i]=p[i-1].second;
}
int ans=0;
for(int i=0;i<=sum;++i)
{
DP(i,X);
ans=max(ans,f[n][n/2][i]);
}
return ans;
}
};