链接：http://codeforces.com/contest/1132
A - Regular Bracket Sequence - [水]
题解：首先 "()" 这个的数量多少是没有关系的，但是 "((" 和 "))" 的数量必须是相等的，再然后如果存在 ")(" 的话，"((" 和 "))" 的数目就必须要大于零。
AC代码：
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d;
int main()
{
cin>>a>>b>>c>>d;
if(a==d)
{
if(c> && a== && d==) cout<<<<endl;
else cout<<<<endl;
}
else cout<<<<endl;
}
B - Discounts - [水]
题意：有 $n$ 块巧克力，每个价格为 $a[i]$，你必须把它们都买完。现在你有 $m$ 张优惠券，一张优惠券可以使你买任意 $q[i]$ 块巧克力并让你免去其中最便宜的那块巧克力的钱，剩下的都要全款买下。你要给出用每张优惠券买完所有巧克力的最少花费。
题解：很显然，如果一张优惠券只能买一块巧克力是最好的，能免去最贵的那块巧克力的钱；能买两个的次之，能免去次贵的巧克力的钱；以此类推。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e5+;
int n,m,a[maxn];
int main()
{
scanf("%d",&n);
ll sum=;
for(int i=;i<=n;i++) scanf("%d",&a[i]), sum+=a[i];
sort(a+,a+n+,greater<int>{});
scanf("%d",&m);
for(int i=,q;i<=m;i++)
{
scanf("%d",&q);
printf("%I64d\n",sum-a[q]);
}
}
C - Painting the Fence- [前缀和优化]
D - Stressful Training - [二分+贪心+优先队列]
E - Knapsack - [DFS]
网上看题解，居然可以搜过去？有点神仙啊……
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; ll w,a[],ans;
void dfs(int p,ll x)
{
if(p==)
{
ans=max(ans,x);
return;
}
ll v=min((w-x)/p,a[p]);
for(int t=;t>;t--) dfs(p+,x+max(0LL,(v--)*p));
}
int main()
{
cin>>w;
for(int i=;i<=;i++) cin>>a[i];
dfs(,);
cout<<ans<<endl;
}
F - Clear the String - [区间DP]
题解：设 $f[l][r]$ 是消除 $[l,r]$ 区间所花的最少次数，对于每次更新：
1、如果 $s[l]=s[r]$，$f[l][r]=min(f[l][r],f[l+1][r−1]+1)$；
2、如果 $s[l] \neq s[r]$，$f[l][r]=min(f[l][r],min(f[l+1][r],f[l][r−1])+1)$
3、枚举中间点 $k=l \sim r$，$f[l][r]=min(f[l][r],f[l][k]+f[k][r]−1)$，这样的话 $k$ 这个点删了两次，所以要减一，因为 $l,k,r$ 可能被同时删去，所以要这样转移。
AC代码：
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=;
int n;
char s[maxn];
int f[maxn][maxn]; int main()
{
cin>>n;
scanf("%s",s+); memset(f,,sizeof(f));
for(int i=;i<=n;i++) f[i][i]=;
for(int len=;len<=n;len++)
{
for(int i=,j=i+len-;j<=n;i++,j++)
{
f[i][j]=INF;
if(s[i]==s[j]) f[i][j]=min(f[i][j],f[i+][j-]+);
else f[i][j]=min(f[i][j],min(f[i+][j],f[i][j-])+);
for(int k=i;k<=j;k++) f[i][j]=min(f[i][j],f[i][k]+f[k][j]-);
}
}
cout<<f[][n]<<endl;
}