1、poj 3267
题意：给你一个字符串，下面有若干单词，问字符串要变成由下面单词组成的字符串，至少要删除多少个字母......
例如：
6 10 browndcodw cow milk white black brown farmer
其中，brown和cow可以组成browncow，这样至少是删除两个字母.......当然，下面的单词可以重复利用......
思路：dp[i]表示历遍到第i个字符时要删除的最少字母数，那么从后面往前面历遍，dp[i]=dp[i+1]+1
若是在i~~lens中，可以找到某个字符串，并且首字母就是i所处位置的字符，那么动态转移dp[i]=min(dp[i],dp[pos]+lens-i-lent);
1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 using namespace std; 5 int dp[1000]; 6 char s[1000],t[605][30]; 7 int main() 8 { 9 int lens,m; 10 while(scanf("%d%d",&m,&lens)>0) 11 { 12 scanf("%s",s); 13 for(int i=0;i<m;i++) 14 scanf("%s",t[i]); 15 dp[lens]=0; 16 for(int i=lens-1;i>=0;i--) 17 { 18 dp[i]=dp[i+1]+1; 19 int lent; 20 for(int j=0;j<m;j++) 21 { 22 lent=strlen(t[j]); 23 int p=0,p1=i; 24 if(s[i]==t[j][0]) 25 while(p<lent&&p1<lens) 26 { 27 if(s[p1]==t[j][p]) 28 { 29 p1++; 30 p++; 31 } 32 else 33 p1++; 34 } 35 if(p==lent) 36 { 37 dp[i]=min(dp[i],dp[p1]+p1-i-lent); 38 } 39 } 40 } 41 printf("%d ",dp[0]); 42 } 43 return 0; 44 }
2、poj 1083（贪心）
题意：有400个房间......房间是这样排的：
就是过道只能容纳一个人过去，而且每一次也只能经过一个人，比如说，4~~6，2~~5，每次去的时候，需要十分钟，那么这样一组数据，需要走20分钟。
但是有个问题，如果是从2~~3，4~~5，这样也是需要20分钟的，因为2~~3要占用1、2过道，4~~5是要占用2、3过道......所以需要20分钟。
思路：开一个记录房间的数组，每次只要走过这些房间，那么就++，然后取最大值就好......
1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 #include<algorithm> 5 using namespace std; 6 struct node 7 { 8 int k,p; 9 }s[5000]; 10 int h[1000]; 11 int main() 12 { 13 int text,cnt=0; 14 scanf("%d",&text); 15 while(text--) 16 { 17 int n; 18 scanf("%d",&n); 19 memset(h,0,sizeof(h)); 20 for(int i=1;i<=n;i++) 21 { 22 int tmp,tmp1; 23 scanf("%d%d",&tmp,&tmp1); 24 25 if(tmp>tmp1) 26 { 27 tmp=tmp+tmp1; 28 tmp1=tmp-tmp1; 29 tmp=tmp-tmp1; 30 } 31 s[i].k=tmp; 32 s[i].p=tmp1; 33 if(s[i].k%2) 34 s[i].k++; 35 if(s[i].p%2) 36 s[i].p++; 37 for(int k=s[i].k;k<=s[i].p;k++) 38 h[k]++; 39 } 40 int sum=0; 41 42 for(int i=1;i<=405;i++) 43 if(h[i]>sum) 44 sum=h[i]; 45 printf("%d ",sum*10); 46 } 47 return 0; 48 }
3、
题目大意：
一套通讯系统由一些设备组成，每种设备由不同的供应商供应，每个供应商供应的同种设备有各自的带宽（bandwidth）和价格（prices）。通讯系统的带宽(B)指的是组成该系统的所有设备的带宽的最小值，通讯系统的价格(P)指的是组成该系统的所有设备的价格之和。求最大的 (B / P)。
思路：好吧，dp[i][j]代表在选择第i种产品，带宽为j的时候的最少价格，在后面，直接历遍i/dp[n][i]，取最大值.......
那么，有，dp[i][j]=min(dp[i][j] , dp[i-1][j] + p)
1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 using namespace std; 5 int dp[105][10010]; 6 struct node 7 { 8 int num; 9 int p; 10 }s[105][105]; 11 int t[105]; 12 int main() 13 { 14 int text; 15 scanf("%d",&text); 16 while(text--) 17 { 18 int n; 19 scanf("%d",&n); 20 //cnt=1; 21 int maxn=0; 22 for(int i=1;i<=n;i++) 23 { 24 int m; 25 scanf("%d",&m); 26 t[i]=m; 27 for(int j=1;j<=m;j++) 28 { 29 scanf("%d%d",&s[i][j].num,&s[i][j].p); 30 if(maxn<s[i][j].num) 31 maxn=s[i][j].num; 32 } 33 34 } 35 for(int i=0;i<=n;i++) 36 for(int j=0;j<=maxn;j++) 37 dp[i][j]=10000000; 38 for(int i=0;i<=maxn;i++) 39 dp[0][i]=0; 40 for(int i=1;i<=n;i++) 41 { 42 for(int j=1;j<=t[i];j++) 43 { 44 for(int k=1;k<=s[i][j].num;k++) 45 dp[i][k]=min(dp[i][k],dp[i-1][k]+s[i][j].p); 46 } 47 } 48 double ans=0; 49 for(int i=1;i<=maxn;i++) 50 if(ans<(i*1.0)/(dp[n][i]*1.0)) 51 ans=(i*1.0)/(dp[n][i]*1.0); 52 printf("%.3lf ",ans); 53 } 54 return 0; 55 }