第二弹并没有比第一弹高到哪里去

而且好多题屯着没写

第二弹只是为了不让文章太长编辑起来太麻烦罢了

第二弹开始辣

BZOJ-1820: [JSOI2010]Express Service 快递服务

先考虑f[i][j][k][w]表示序列第i次，三位快递员在j,k,w

但是由于有一位快递员必定在序列i的位置，所以这样我们可以缩掉一维

考虑快递员位置的顺序无关紧要，所以我们可以令 k>=j

现在我们只用考虑f[i][j][k]，三位快递员分别在a[i],j,k, 其中a[i]为读入的位置

考虑到三维的数组炸空间，我们就可以滚滚滚辣

不能算卡着过吧QAQ

#include <bits/stdc++.h>
using namespace std;
const int NN = 1005;
#define INF 0x3f3f3f3f
int ans,la,t,m,n,f[2][NN][NN],a[NN],mp[NN][NN];

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i)
		for (int j=1;j<=n;++j) scanf("%d",&mp[i][j]);
	m = 0;
	while (scanf("%d",&a[++m])!=EOF);
	la = 1, t = 0;
	memset(f,0x3f,sizeof(f));
	f[t][1][2] = mp[3][a[1]];
	f[t][1][3] = mp[2][a[1]];
	f[t][2][3] = mp[1][a[1]];
	for (int i=2;i<m;++i)
	{
		la ^= 1, t ^= 1;
		memset(f[t],0x3f,sizeof(f[t]));
		for (int j=1;j<=n;++j)
			for (int k=j;k<=n;++k)
			{
				f[t][j][k] = f[t][k][j] = min(f[t][j][k],f[la][j][k]+mp[a[i-1]][a[i]]);
				f[t][k][a[i-1]] = f[t][a[i-1]][k] = min(f[t][a[i-1]][k],f[la][j][k] + mp[j][a[i]]);
				f[t][j][a[i-1]] = f[t][a[i-1]][j] = min(f[t][a[i-1]][j],f[la][j][k] + mp[k][a[i]]);
			}
	}
	ans = INF;
	for (int i=1;i<=n;++i)
		for (int j=i;j<=n;++j) ans = min(ans,f[t][i][j]);
	printf("%d\n",ans);  
	return 0;
}

BZOJ-3191: [JLOI2013]卡牌游戏

要对剩余的人进行重新标号

f[i][j]表示剩余i个人，第j个人的获胜概率。

在任何时刻我们的庄家都标成第一个人。只是此时的第一个人不见得是刚开始的第一个人罢了。

这样我们就可以枚举所有的决策，同时求出谁狗带了，记为now。

然后重新标号，此时第j个人在重标号后为$(j+i-now)%i$。

最后，末位不能有空格！末位不能有空格！末位不能有空格！（好像是第一次PE）

BZOJ上第二组样例输出好像狗带了

百分号输出要打两个QAQ

#include <bits/stdc++.h>
using namespace std;
int n,m,a[55],now;
double f[55][55];
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;++i) scanf("%d",&a[i]);
	f[1][1] = 1;
	for (int i=2;i<=n;++i)
		for (int j=1;j<=i;++j)
			for (int k=1;k<=m;++k)
			{
				now = (a[k]-1) % i + 1;
				if (now == j) continue;
				now = (j+i-now) % i;
				f[i][j] += f[i-1][now] / (double) m;
			}
	printf("%.2lf%%",f[n][1]*100);
	for (int i=2;i<=n;++i) printf(" %.2lf%%",f[n][i]*100);
	puts("");
	return 0;
}

BZOJ-2431: [HAOI2009]逆序对数列

用f[i][j]表示前i个数j个逆序对

容易得到$f[i][j]=\sum_{k=0}^{i-1}dp[i-1][j-k]$

前缀和优化搞一搞

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

const int mod = 10000,NN = 1005;
int f[NN][NN],s[NN][NN],n,k;

int main()
{
	scanf("%d%d",&n,&k);
	f[1][0] = 1;
	for (int i=0;i<=k;++i) s[1][i] = 1;
	for (int i=2;i<=n;++i)
	{
		for (int j=0;j<=k;++j)
		{
			f[i][j] = s[i-1][j];
			if (j-i >= 0) f[i][j] -= s[i-1][j-i];
			f[i][j] = (f[i][j]+mod) % mod;
		}
		s[i][0] = 1;
		for (int j=1;j<=k;++j) s[i][j] = (s[i][j-1] + f[i][j]) % mod;
	}
	printf("%d\n",f[n][k]);
	return 0;
}

BZOJ-1966: [Ahoi2005]VIRUS 病毒检测

$n^{3}$就能水过了吧

把*和?分开来做

f[i][j]表示两个字符串分别匹配到第i位和第j位的时候符合

#include <bits/stdc++.h>
using namespace std;
char ch[1010],chh[505];
bool f[1010][505];
int c[1010],len,lenn,ans = 0,n;
bool Jug(char xx,char yy)
{
    if (xx == yy || xx == '?') return 1;
    return 0;
}

void Work()
{
    memset(f,0,sizeof(f));
    memset(c,0x3f,sizeof(c));
    f[0][0] = 1;
    for (int i=1;i<=len;++i)
    {
        if (ch[i] != '*')
            for (int j=1;j<=lenn;++j)
            {
                if (f[i-1][j-1] && Jug(ch[i],chh[j])) f[i][j] = 1;
                else
                if (i!=1 && ch[i-1] == '*' && c[i-1]<j && Jug(ch[i],chh[j])) f[i][j] = 1;
            }
        else
        {
            if (i == 1) f[1][0] = 1;
            for (int j=1;j<=lenn;++j)
            {
                f[i][j] = f[i-1][j] || f[i][j-1];
                if (f[i][j]) c[i] = min(c[i],j);
            }
        }
    }
    if (!f[len][lenn]) ++ans;
}

int main()
{
    ans = 0;
    scanf("%s",ch+1);
    len = strlen(ch+1);
    scanf("%d",&n);
    while (n--)
    {
        scanf("%s",chh+1);
        lenn = strlen(chh+1);
        Work();
    }
    printf("%d\n",ans);
    return 0;
}

BZOJ-1044：[HAOI2008]木棍分割

第一问[TM怎么这么像去年联赛题啊(╯‵□′)╯︵┻━┻]二分+贪心判断

第二问加个队列搞一搞差不多了

#include <bits/stdc++.h>
using namespace std;
const int NN = 100005,mod = 10007;  
int a[NN],sum[NN],l,r,n,m,ans = 0,q[NN],f[2][NN],anss = 0,pre,la,h,t,tot;
bool Jug(int xx)
{
    int cnt = 0, s = 0;
    for (int i=1;i<=n;++i)
    {
        if (a[i] > xx) return 0;
        s += a[i];
        if (s > xx) { s = a[i], cnt++;}
        if (cnt > m) return 0;
    }
    return 1;
}
 
void Solve1()
{
    l = 1, r = sum[n];
    while (l<=r)
    {
        int mid = (l+r)>>1;
        if (Jug(mid)) ans = mid, r = mid-1;
            else l = mid+1;
    }
    printf("%d ",ans);
}
void Solve2()
{
    pre=0,la=1,tot=0;
    f[0][0] = 1;
    for (int i=1;i<=m;++i)
    {
        h = t = 1;
        pre ^= 1, la ^= 1;
        q[t] = 0, tot = f[la][0];
        for (int j=1;j<=n;++j)
        {
            while (h<=t && sum[j] - sum[q[h]] > ans)
            {
                tot = (tot - f[la][q[h]] + mod) % mod;
                ++h;
            }
            f[pre][j] = tot;
            q[++t] = j;
            tot = (tot + f[la][j]) % mod;
        }
        for (int j=n-1;j>=1;--j)
        {
            if (sum[n] - sum[j] > ans) break;
            anss = (anss + f[pre][j]) % mod;
        }
        memset(f[la],0,sizeof(f[la]));
    }
    printf("%d\n",anss);
}
 
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i) scanf("%d",&a[i]),sum[i] = sum[i-1] + a[i];
    Solve1();
    Solve2();
    return 0;
}

BZOJ-1076：[SCOI2008]奖励关

期望+状压？！

f[i][j]表示第i步j状态下的期望

这一步的期望=(上一步的期望+这一步的得分)/n  （听说倒着推方便）

#include <bits/stdc++.h>
using namespace std;
int bin[20],d[20],v[20],x,n,m;
double f[101][65536];
int main()
{
    scanf("%d%d",&m,&n);
    for (int i=0;i<=16;++i) bin[i] = 1<<i;
    for (int i=1;i<=n;++i)
    {
        scanf("%d%d",&v[i],&x);
        while (x)
        {
            d[i] += bin[x];
            scanf("%d",&x);
        }
    }
    for (int i=m;i>=1;--i)
        for (int j=0;j<=bin[n+1]-1;++j)
        {
            for (int k=1;k<=n;++k)
                if ((d[k]&j) == d[k])
                    f[i][j] += max(f[i+1][j], f[i+1][j|bin[k]] + v[k]);
                else f[i][j] += f[i+1][j];
            f[i][j] /= (double)n;
        }
    printf("%.6lf",f[1][0]);
    return 0;
}

BZOJ-1879: [Sdoi2009]Bill的挑战

先状压

f[i][j]表示i个字符都匹配好了时状态为j的方案数

#include <bits/stdc++.h>
using namespace std;
#define mod 1000003
int T,n,k,l,N,ans;
char ch[16][55];
int f[55][1<<15],g[55][27];
int main()
{
    for (scanf("%d",&T);T;T--)
    {
        scanf("%d%d",&n,&k);
        memset(f,0,sizeof(f)); memset(g,0,sizeof(g));
        for (int i=0;i<n;++i) scanf("%s",ch[i]);
        N = 1<<n;
        l = strlen(ch[0]);
        f[0][N-1] = 1; ans = 0;
        for (int i=0;i<l;++i)
            for (char c='a';c<='z';++c)
                for (int k=0,s=1;k<n;++k,s<<=1) 
                    if (ch[k][i] == '?' || ch[k][i] == c) g[i][c-'a'] |= s;
        for (int i=0;i<l;++i)
            for (int j=0;j<N;++j)
                if (f[i][j])
                    for (char c='a';c<='z';++c)
                        f[i+1][j&g[i][c-'a']] += f[i][j], f[i+1][j&g[i][c-'a']] %= mod;
        for (int cnt =0,i=0;i<N;++i)
        {
            cnt = 0;
            for (int j=1;j<N;j<<=1) cnt += (bool) (i&j);
            if (cnt == k) ans = (ans + f[l][i]) % mod;
        }
        printf("%d\n",ans);
    }
    return 0;
}

BZOJ-1925: [Sdoi2010]地精部落

想不出，看题解（不以为耻反以为荣QAQ）~~~~(>_<)~~~~

#include <bits/stdc++.h>
using namespace std;
int t,ans,n,mod,f[2][4205];
int main()
{
    scanf("%d%d",&n,&mod);
    f[0][2] = 1;
    t = 0;
    for (int i=3;i<=n;++i)
    {
        t ^= 1;
        for (int j=1;j<=i;++j)
        {
            f[t][j] = (f[t][j-1] + f[t^1][i-j+1]) % mod;
        }
    }
    for (int i=1;i<=n;++i)
    {
        ans = (ans + f[t][i]) % mod;
    }
    ans = (ans * 2) % mod;
    printf("%d\n",ans);
    return 0;
}

BZOJ-3174: [Tjoi2013]拯救小矮人

a[i]和b[i]加起来，从小到大排序。因为越大的到最后越容易自救。

设f[i]为所有人中跑出去i个人后塔的最高高度，尽量高就可以让更多的人出去辣

#include <bits/stdc++.h>
using namespace std;
 
struct REC
{
    int a,b;
}c[2005];
 
int sum,h,n,ans,f[2005];
 
bool cmp(REC xx,REC yy)
{
    return (xx.a+xx.b) < (yy.a + yy.b);
}
 
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;++i) scanf("%d%d",&c[i].a,&c[i].b), sum += c[i].a;
    sort(c+1,c+1+n,cmp);
    memset(f,-1,sizeof(f));
    scanf("%d",&h);
    f[0] = sum;
    ans = 0;
    for (int i=1;i<=n;++i)
    {
        for (int j=ans;j>=0;--j)
            if (f[j] + c[i].b >= h) f[j+1] = max(f[j+1],f[j]-c[i].a);
        if (f[ans+1] >= 0) ans++;
    }
    printf("%d\n",ans);
    return 0;
}

怎么有一种又一次任务完成的错觉