当前位置: 首页 > 工具软件 > vans > 使用案例 >

USACO6.1.1Postal Vans(vans)

陈淳
2023-12-01

插头dp(基于连通性状态压缩的动态规划)问题

 什么是插头dp看陈丹琪的论文,她的写法也是目前为止的标准写法吧

http://wenku.baidu.com/link?url=VGHZwf6zGOFGKRN8DCKHPi6BJApgXYBsnk2CDXByfOYmwxToQoOJWi64MgEf1v5qWRuounu4y8xT_T_UuJb-XuYvjEgAzjRhaUK6HPO6szK

对于这道题,4行n列,按列来做的话每一列只有四个格子,状态就可以手动枚举了,状态转移也很方便,减少了很多代码量,算是取巧吧,大多数题还是只能按照论文里说的那么写了

注意:网格上的dp,状态无疑会很多,答案一定很多,所以自己得写高精,高精和输出直接写到struct里无疑方便很多


/*
ID:xsy97051
LANG:C++
TASK:vans
*/
#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

#define INF 6
/* ####
 (()) ()() ()## (##) ##() #()#
*/
const bool link[INF][INF]=
          {{1,0,1,0,1,0},
           {0,1,0,1,0,0},
           {0,1,0,1,0,0},
           {1,0,1,0,1,1},
           {0,1,0,1,0,0},
           {0,0,0,1,0,0}};

struct NUM
{
    int n[500];
    int l;
    void set(int t)
    {
        memset(n,0,sizeof(n));
        n[0]=t;
        l=1;
    }
   	void operator += (const NUM haha)
    {
        if(haha.l>l)		l=haha.l;
        for(int i=0;i<l;++i)
        {
            n[i]+=haha.n[i];
            if(n[i]>9)	
			{
				++n[i+1];
				n[i]-=10;	
			}
        }
        if(n[l])	++l;
    }
    void print()
    {
    	for(int i=l-1;i>=0;i--)
    		cout<<n[i];
    	cout<<endl;
    }
};
NUM f[2][INF];

int main()
{
	freopen("vans.in","r",stdin);
	freopen("vans.out","w",stdout);
	int n;
	cin>>n;
	NUM ans;
	ans.set(0);
	if(n!=1)
	{
		int old=1,now=0;
		f[0][2].set(1);
		f[0][3].set(1);
		for(int i=1;i<n;++i)
       	{
            old^=1;	now^=1;
            for(int j=0;j<INF;++j)
            f[now][j].set(0);
            
            for(int j=0;j<INF;++j)
                for(int k=0;k<INF;++k)
                    if(link[j][k])
                    f[now][k]+=f[old][j];
        }
        ans+=f[now][2];
        ans+=f[now][4];
	}
	ans.print();
	return 0;
}


 类似资料:

相关阅读

相关文章

相关问答