Invoker(小DP)

摘要:
Pid=6739尝试连接它们。

题意:http://acm.hdu.edu.cn/showproblem.php?pid=6739

尽量让他们连起来。

思路:

直接dp,其中一个状态是以什么结尾。

  1 #define IOS ios_base::sync_with_stdio(0); cin.tie(0);
  2 #include <cstdio>//sprintf islower isupper
  3 #include <cstdlib>//malloc  exit strcat itoa system("cls")
  4 #include <iostream>//pair
  5 #include <fstream>//freopen("C:\Users\13606\Desktop\草稿.txt","r",stdin);
  6 #include <bitset>
  7 //#include <map>
  8 //#include<unordered_map>
  9 #include <vector>
 10 #include <stack>
 11 #include <set>
 12 #include <string.h>//strstr substr
 13 #include <string>
 14 #include <time.h>//srand(((unsigned)time(NULL))); Seed n=rand()%10 - 0~9;
 15 #include <cmath>
 16 #include <deque>
 17 #include <queue>//priority_queue<int, vector<int>, greater<int> > q;//less
 18 #include <vector>//emplace_back
 19 //#include <math.h>
 20 //#include <windows.h>//reverse(a,a+len);// ~ ! ~ ! floor
 21 #include <algorithm>//sort + unique : sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare)
 22 using namespace std;//next_permutation(a+1,a+1+n);//prev_permutation
 23 //******************
 24 int abss(int a);
 25 int lowbit(int n);
 26 int Del_bit_1(int n);
 27 int maxx(int a,int b);
 28 int minn(int a,int b);
 29 double fabss(double a);
 30 void swapp(int &a,int &b);
 31 clock_t __STRAT,__END;
 32 double __TOTALTIME;
 33 void _MS(){__STRAT=clock();}
 34 void _ME(){__END=clock();__TOTALTIME=(double)(__END-__STRAT)/CLOCKS_PER_SEC;cout<<"Time: "<<__TOTALTIME<<" s"<<endl;}
 35 //***********************
 36 #define rint register int
 37 #define fo(a,b,c) for(rint a=b;a<=c;++a)
 38 #define fr(a,b,c) for(rint a=b;a>=c;--a)
 39 #define mem(a,b) memset(a,b,sizeof(a))
 40 #define pr printf
 41 #define sc scanf
 42 #define ls rt<<1
 43 #define rs rt<<1|1
 44 typedef long long ll;
 45 const double E=2.718281828;
 46 const double PI=acos(-1.0);
 47 //const ll INF=(1LL<<60);
 48 const int inf=(1<<30);
 49 const double ESP=1e-9;
 50 const int mod=(int)1e9+7;
 51 const int N=(int)1e5+10;
 52 
 53 int dp[N][50];
 54 char s[N];
 55 int tot;
 56 int ID[400];
 57 int map[50];
 58 int id(int x)
 59 {
 60     return ID[x];
 61 }
 62 struct node
 63 {
 64     int a,b,c;
 65 }p[10];
 66 void PR(int _[],int n)
 67 {
 68     for(int i=1;i<=n;++i)
 69         pr("%d ",_[i]);
 70     pr("
");
 71 }
 72 int main()
 73 {
 74     tot=0;
 75     for(int i=1;i<=350;++i)
 76     {
 77         int temp=i;
 78         bool f=1;
 79         while(temp>0)
 80         {
 81             if(temp%10!=1&&temp%10!=2&&temp%10!=3)
 82                 f=0;
 83             temp/=10;
 84         }
 85         if(f)map[++tot]=i;
 86     }
 87     for(int i=1;i<=45;++i)
 88         ID[map[i]]=i;
 89     p[1]={1,2,3};
 90     p[2]={1,3,2};
 91     p[3]={2,1,3};
 92     p[4]={2,3,1};
 93     p[5]={3,1,2};
 94     p[6]={3,2,1};
 95     int v[200];
 96     v['Y']=111;
 97     v['V']=112;
 98     v['G']=113;
 99     v['C']=222;
100     v['X']=122;
101     v['Z']=223;
102     v['T']=333;
103     v['F']=133;
104     v['D']=233;
105     v['B']=123;
106     while(~sc("%s",s+1))
107     {
108         int l=strlen(s+1);
109         for(int i=1;i<=l;++i)
110             for(int j=1;j<=45;++j)
111                 dp[i][j]=inf;
112         for(int i=1;i<=6;++i)
113         {
114             int temp=v[s[1]];
115             int cnt=3;
116             int mp[5];
117             while(temp>0)
118             {
119                 mp[cnt]=temp%10;
120                 temp/=10;
121                 cnt--;
122             }
123             int x=mp[p[i].b]*10+mp[p[i].c];
124             dp[1][id(mp[p[i].a]*100+mp[p[i].b]*10+mp[p[i].c])]=min(3,dp[1][id(mp[p[i].a]*100+mp[p[i].b]*10+mp[p[i].c])]);
125             dp[1][id(x)]=min(dp[1][id(x)],3);
126             x=mp[p[i].c];
127             dp[1][id(x)]=min(dp[1][id(x)],3);
128         }
129         //PR(dp[1],37);
130         int ans=0;
131         for(int i=2;i<=l+1;++i)
132         {
133             int min_=inf;
134             for(int j=1;j<=45;++j)
135                 min_=min(min_,dp[i-1][j]);
136             ans=min_;
137             if(i==l+1)break;
138 
139             int temp=v[s[i]];
140             int cnt=3;
141             int mp[5];
142             while(temp>0)
143             {
144                 mp[cnt]=temp%10;
145                 temp/=10;
146                 cnt--;
147             }
148             for(int j=1;j<=6;++j)
149             {
150                 int x=mp[p[j].a],y=mp[p[j].b],z=mp[p[j].c];
151             //    cout<<x<<' '<<y<<' '<<z<<endl;
152                 dp[i][id(x*100+y*10+z)]=min(dp[i][id(x*100+y*10+z)],min(min(dp[i-1][id(x)]+2,min(min_+3,dp[i-1][id(x*10+y)]+1)),dp[i-1][id(x*100+y*10+z)]));
153                 dp[i][id(y*10+z)]=min(dp[i][id(y*10+z)],min(min(dp[i-1][id(x)]+2,min(min_+3,dp[i-1][id(x*10+y)]+1)),dp[i-1][id(x*100+y*10+z)]));
154                 dp[i][id(z)]=min(dp[i][id(z)],min(min(dp[i-1][id(x)]+2,min(min_+3,dp[i-1][id(x*10+y)]+1)),dp[i-1][id(x*100+y*10+z)]));
155             }
156         //    PR(dp[i],37);
157         }
158         pr("%d
",ans+l);
159     }
160     return 0;
161 }
162 
163 /**************************************************************************************/
164 
165 int maxx(int a,int b)
166 {
167     return a>b?a:b;
168 }
169 
170 void swapp(int &a,int &b)
171 {
172     a^=b^=a^=b;
173 }
174 
175 int lowbit(int n)
176 {
177     return n&(-n);
178 }
179 
180 int Del_bit_1(int n)
181 {
182     return n&(n-1);
183 }
184 
185 int abss(int a)
186 {
187     return a>0?a:-a;
188 }
189 
190 double fabss(double a)
191 {
192     return a>0?a:-a;
193 }
194 
195 int minn(int a,int b)
196 {
197     return a<b?a:b;
198 }

免责声明:文章转载自《Invoker(小DP)》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇SOS--DP(基础版本)未压缩空间[CC-STREETTA]The Street下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

上传图片之上传前预览图片

上传图片对图片进行一下预览,可以了解图片上传后大概会是什么样子,此功能用js实现,然后在fileupload控件的change事件中调用,这样当用fileupload选择完图片以后,图片就会自动显示出来了。功能很简单,却很实用。 预览图片的js代码: <script type="text/javascript"> function s...

Swing菜单与工具栏(二)

6.1.4 JMenuItem类 JMenuItem组件是用户可以在菜单栏上选择的预定义组件。作为AbstractButton的子类,JMenuItem是一个特殊的按钮组件,其行为类似于JButton。除了作为AbstractButton的子类,JMenuItem类共享JButton的数据模型(ButtonModel接口与DefaultButtonModel...

shell脚本实现每秒执行一次任务 rsync命令使用

shell脚本实现每秒执行一次任务 rsync命令使用 - 技术博客 - 博客频道 - CSDN.NET shell脚本实现每秒执行一次任务 rsync命令使用 分类:分布式系统2012-03-29 14:24103人阅读评论(0)收藏举报 目的:编写脚本没秒钟同步一个log数据 1.编写shell脚本 vi /tmp/ceshi.sh#!/bin/...

艾伟:10分钟去除天天团购系统版权 狼人:

刚有个朋友说他的公司最近想弄个团购项目,用的程序是天天团购系统,程序架好后网页底部有天天团购的版权,他说搜索了文件和数据库都没有找到这个版权的代码是哪里,就让我帮忙看看,嗯,那我们就一起来看看吧,如下: 打开首页 查看HTML代码 分析:这个版权代码是加在代码的结尾,经验断定这段代码不在模板文件中也不在数据库文件中,咱们去业务逻辑代码中找,找了一会儿发现m...

程序即人生 » 移动平台现在可用的C++ 11特性

程序即人生 » 移动平台现在可用的C++ 11特性 移动平台现在可用的C++ 11特性 2011年12月29日jtianling 发表评论阅读评论542 人阅读 移动平台特指iOS和Android,并且Android使用的是NDK,因为开发的时候是在Win32平台下,所以还需要考虑VS的支持。 当前(2011-12-21)最新的版本: Win32:...

伍迷创意随想集 之 杯具拥有个性,个性成就杯具 伍迷 博客园

伍迷创意随想集 之 杯具拥有个性,个性成就杯具 - 伍迷 - 博客园 伍迷创意随想集 之 杯具拥有个性,个性成就杯具 当你在生活中发现不方便、不舒服的时候,其实也就是你发挥创意的时候——伍迷看到标题,可能不少朋友以为我要谈的是近一年的悲剧谐音词“杯具”,可今天我要谈的,其实是真杯具,而非假“杯具”也。起因:一人请多位朋友到家聚会,来到家中,自然要沏茶倒水...