Topcoder SRM 605 div1 题解
Easy（250pts）：
题目大意：你有n种汉堡包（统统吃掉～），每一种汉堡包有一个type值和一个taste值，你现在要吃掉若干个汉堡包，使得它们taste的总和*（不同的type值的个数）乘积越大，输出这个最大值。数据满足n<=50,type<=100,abs(taste)<=100000。
这题好像是个贪心，才不是呢啊哼～
首先我们发现，如果若干个汉堡包有同一个type值，那么我们可以把这一些汉堡包看成一个新的大汉堡包，它的type就是原来的type，它的taste就是取原先至少一个的最大taste之和，显然这一步是可以O(n)预处理完成的。
然后由于type不是很大，我们可以枚举我们选取了多少个type，
如果选择了k个type，那么一定是选择了taste最大的k个，然后乘以下，扫一遍k就好了。
时间复杂度O(n^2)，代码如下：
Medium（450pts）：
题目大意：有2n个数1~2n，现在把它们分成两个集合A和B，满足A和B都有n个元素，且A中第i小的元素和B中第i小的元素的差的绝对值至少为K，求方案数，数据满足n<=50,K<=10。
我实在没有搞懂，为什么这题450分。。。
比较显然是个dp吧，我们来考虑怎么来描述一个状态，
在每一个状态下，都有两种数，第一种是已经被匹配的了，第二种是还没有被匹配的，
而没有被匹配的也有两种，
我们从大到小进行匹配，假设当前进行匹配的数为i，那么未被匹配的数一共有两种，
第一种是大于等于i+K的数，这些数可以随意被匹配，
第二种是i+1~i+K-1这些数，这些数不能和i匹配，
这两种数中，第一种数我们只关心它的个数，第二种则要关心位置，需要用2^k种状态描述出来，
然后直接转移就可以了，
时间复杂度O(n^2*2^K)，代码如下：
Hard（1000pts）：
题目大意：现在有一个数列，它是1~n的一个排列，我们每次可以进行一次操作：选取一段l~r，将l~r的数都变成l~r的最大值，现在可以进行不超过K次操作，求最后一共有多少种不同的可能。数据满足n<=200,k<=200。
怎么这题又是dp呀，自古TC出DP～
在dp之前，我们需要对这个奇奇怪怪的操作挖掘一些性质。
首先，一开始的n个数是不相同的，所以在整个操作过程中的任何时刻，相同的数永远都是连续的一段。
其次，在某次操作前，i的一段在j的一段的前面，那么操作之后i的这一段依然在j的这一段的前面。
有了这两个性质，差不多就可以dp了，我们考虑如何表述一个状态。
k表示当前最多可以操作几步，i表示当前从小到大判定第几个数，j表示新的数列的前j个数已经被确定，
那么我们就有f[k][i][j]=sigma(f[k-1][i-1][r])。
然而这样是O(n^4)的，对于n<=200显然会爆炸，我们考虑进行进一步的优化，
我们预处理出第i为什么情况下能变成j，那么一定是在原数列中，这两个数位置之前的数都小于等于j，
这样我们可以先预处理出某个位置可以变成什么数，时间复杂度O(n^3)，
然后我们继续dp，除了上面描述的k,i,j，我们再用一个state表示当前是否处于匹配状态，显然state只能是true或者false，
于是考虑f[k][i][j][state]：
如果j>n，那么这已经是一个合法方案了，直接返回1；
如果i>n，那么这个方案不合法，直接返回0；
如果这两种情况都不满足，那么有两种情况：
第一种是当前数i不参与匹配，对答案贡献度是f[k][i+1][j][false]；
第二种是当前数i参与匹配，我们没有必要再枚举它匹配到哪个位置，直接f[k-1][i][j+1][true]就可以了。
这里dp就完成了，时间复杂度O(n^3)。
所以整个题时间复杂度O(n^3)，代码如下：
题目大意：你有n种汉堡包（统统吃掉～），每一种汉堡包有一个type值和一个taste值，你现在要吃掉若干个汉堡包，使得它们taste的总和*（不同的type值的个数）乘积越大，输出这个最大值。数据满足n<=50,type<=100,abs(taste)<=100000。
这题好像是个贪心，才不是呢啊哼～
首先我们发现，如果若干个汉堡包有同一个type值，那么我们可以把这一些汉堡包看成一个新的大汉堡包，它的type就是原来的type，它的taste就是取原先至少一个的最大taste之和，显然这一步是可以O(n)预处理完成的。
然后由于type不是很大，我们可以枚举我们选取了多少个type，
如果选择了k个type，那么一定是选择了taste最大的k个，然后乘以下，扫一遍k就好了。
时间复杂度O(n^2)，代码如下：
#include <bits/stdc++.h>
#define Maxn 107
#define inf 10000007
using namespace std;
int f[Maxn],g[Maxn];
int cnt1,cnt2,n;
class AlienAndHamburgers
{
public:
int getNumber(vector <int> type, vector <int> taste)
{
n=type.size();
for (int i=1;i<=100;i++)
f[i]=-inf;
for (int i=0;i<n;i++)
if (f[type[i]]<0) f[type[i]]=max(f[type[i]],taste[i]);
else if (taste[i]>0) f[type[i]]+=taste[i];
sort(f+1,f+100+1);
memset(g,0,sizeof(g));
g[100]=f[100];
for (int i=100-1;i;i--)
g[i]=f[i]+g[i+1];
//g[100+1-i] now means the most taste[i] can get to choose i types of food
int ans=0;
for (int i=1;i<=100;i++)
if (f[100+1-i]>-inf&&g[100+1-i]>0) ans=max(ans,g[100+1-i]*i);
return ans;
}
};
Medium（450pts）：
题目大意：有2n个数1~2n，现在把它们分成两个集合A和B，满足A和B都有n个元素，且A中第i小的元素和B中第i小的元素的差的绝对值至少为K，求方案数，数据满足n<=50,K<=10。
我实在没有搞懂，为什么这题450分。。。
比较显然是个dp吧，我们来考虑怎么来描述一个状态，
在每一个状态下，都有两种数，第一种是已经被匹配的了，第二种是还没有被匹配的，
而没有被匹配的也有两种，
我们从大到小进行匹配，假设当前进行匹配的数为i，那么未被匹配的数一共有两种，
第一种是大于等于i+K的数，这些数可以随意被匹配，
第二种是i+1~i+K-1这些数，这些数不能和i匹配，
这两种数中，第一种数我们只关心它的个数，第二种则要关心位置，需要用2^k种状态描述出来，
然后直接转移就可以了，
时间复杂度O(n^2*2^K)，代码如下：
#include <bits/stdc++.h>
#define modp 1000000007
#define Maxn 107
#define Maxk 10
using namespace std;
int f[Maxn][Maxn][1<<Maxk];
bool vis[Maxn][Maxn][1<<Maxk];
int n,k;
class AlienAndSetDiv1
{
int tryit(int i, int j, int t)
{
//i means how many numbers left now
//j means how many numbers in set A can be free-matched
//t means the condition of the numbers in set A that cannot be free-matched
if (vis[i][j][t]) return f[i][j][t];
vis[i][j][t]=true;
int res=0;
if (i==0)
{
if (j==0&&t==0) res=1;
f[i][j][t]=res;
return res;
}
if (j==0&&t==0)
{
//all the i numbers are matched now
if (k==1) res=tryit(i-1,1,0); else res=tryit(i-1,0,1);
res=(2LL*res)%modp;
f[i][j][t]=res;
return res;
}
if (j>0)
{
//i get matched with a free-matched one
int nowt=2*t,nowj=j-1;
//the biggest one become free-matched
if (nowt&(1<<(k-1)))
{
nowt-=1<<(k-1);
++nowj;
}
res=(res+tryit(i-1,nowj,nowt))%modp;
}
int nowt=2*t+1,nowj=j;
if (nowt&(1<<(k-1)))
{
nowt-=1<<(k-1);
++nowj;
}
res=(res+tryit(i-1,nowj,nowt))%modp;
f[i][j][t]=res;
return res;
}
public:
int getNumber(int N, int K)
{
n=N,k=K;
memset(vis,false,sizeof(vis));
memset(f,0,sizeof(f));
return tryit(2*n,0,0);
}
};
Hard（1000pts）：
题目大意：现在有一个数列，它是1~n的一个排列，我们每次可以进行一次操作：选取一段l~r，将l~r的数都变成l~r的最大值，现在可以进行不超过K次操作，求最后一共有多少种不同的可能。数据满足n<=200,k<=200。
怎么这题又是dp呀，自古TC出DP～
在dp之前，我们需要对这个奇奇怪怪的操作挖掘一些性质。
首先，一开始的n个数是不相同的，所以在整个操作过程中的任何时刻，相同的数永远都是连续的一段。
其次，在某次操作前，i的一段在j的一段的前面，那么操作之后i的这一段依然在j的这一段的前面。
有了这两个性质，差不多就可以dp了，我们考虑如何表述一个状态。
k表示当前最多可以操作几步，i表示当前从小到大判定第几个数，j表示新的数列的前j个数已经被确定，
那么我们就有f[k][i][j]=sigma(f[k-1][i-1][r])。
然而这样是O(n^4)的，对于n<=200显然会爆炸，我们考虑进行进一步的优化，
我们预处理出第i为什么情况下能变成j，那么一定是在原数列中，这两个数位置之前的数都小于等于j，
这样我们可以先预处理出某个位置可以变成什么数，时间复杂度O(n^3)，
然后我们继续dp，除了上面描述的k,i,j，我们再用一个state表示当前是否处于匹配状态，显然state只能是true或者false，
于是考虑f[k][i][j][state]：
如果j>n，那么这已经是一个合法方案了，直接返回1；
如果i>n，那么这个方案不合法，直接返回0；
如果这两种情况都不满足，那么有两种情况：
第一种是当前数i不参与匹配，对答案贡献度是f[k][i+1][j][false]；
第二种是当前数i参与匹配，我们没有必要再枚举它匹配到哪个位置，直接f[k-1][i][j+1][true]就可以了。
这里dp就完成了，时间复杂度O(n^3)。
所以整个题时间复杂度O(n^3)，代码如下：
#include <bits/stdc++.h>
#define Maxn 207
#define modp 1000000007
using namespace std;
int f[Maxn][Maxn][Maxn][2];
bool vis[Maxn][Maxn][Maxn][2];
bool check[Maxn][Maxn];
int p[Maxn];
int n,k;
class AlienAndPermutation
{
int tryit(int k, int i, int j, int state)
{
if (vis[k][i][j][state]) return f[k][i][j][state];
vis[k][i][j][state]=true;
if (j>n)
{
//the situation is valid
f[k][i][j][state]=1;
return f[k][i][j][state];
}
if (i>n)
{
//the situation is invalid
f[k][i][j][state]=0;
return f[k][i][j][state];
}
//the ith number isn't used
int res=tryit(k,i+1,j,0);
//the ith number is used
if (check[i][j])
{
if (state==1||(i==j)) res=(res+tryit(k,i,j+1,state))%modp;
else if (k>0) res=(res+tryit(k-1,i,j+1,1))%modp;
}
f[k][i][j][state]=res;
return res;
}
public:
int getNumber(vector <int> P, int K)
{
n=P.size(),k=K;
for (int i=1;i<=n;i++) p[i]=P[i-1];
memset(check,true,sizeof(check));
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
for (int t=min(i,j);t<=i||t<=j;t++)
if (p[t]>p[i]) check[i][j]=false;
memset(f,0,sizeof(f));
memset(vis,false,sizeof(vis));
return tryit(k,1,1,0);
}
};
