poj3616
题意:奶牛在1到n时间段内产奶，总共有m个产奶区间，买个区间有开始时间和结束时间，还有产奶量，同时每次产完奶需要休息一定的时间，求最大产奶量
分析:比较简单的dp，有点像最长上升子序列的变种，把产奶时间按开始时间排序，对于开始时间大于前面结束时间的点，求其最大的产奶量
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 #include <vector> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <bitset> 10 #include <cmath> 11 #include <queue> 12 #include <stack> 13 using namespace std; 14 const int maxn=1500; 15 int dp[maxn]; 16 typedef struct p 17 { 18 int start,over,value; 19 }p; 20 int n,m,r; 21 bool cmp(p a,p b) 22 { 23 return a.start<b.start; 24 } 25 int main() 26 { 27 while(cin>>n>>m>>r) 28 { 29 p s[maxn]; 30 for(int i=0;i<m;i++) 31 { 32 cin>>s[i].start>>s[i].over>>s[i].value; 33 s[i].over+=r; 34 } 35 sort(s,s+m,cmp); 36 memset(dp,0,sizeof(dp)); 37 for(int i=0;i<m;i++) 38 { 39 dp[i]=s[i].value; 40 for(int j=0;j<i;j++){ 41 if(s[i].start>=s[j].over) 42 dp[i]=max(dp[i],dp[j]+s[i].value); 43 } 44 } 45 int mx=0; 46 for(int i=0;i<m;i++) 47 mx=max(mx,dp[i]); 48 cout<<mx<<endl; 49 } 50 return 0; 51 }
有关划分数的问题:
n个无区别的物体，划分成不超过m组，求划分方法数。
分析:这个问题被称为n的m划分。设n的m划分是ai,(i=1.....m)(a1+a2+...+am=n)，若没个ai>0，则｛ai-1}对应n-m的m划分。若存在ai=0，则对应了n的m-1划分。令dp[i][j]为j的i划分,dp[i][j]=dp[i-1][j]+dp[i][j-i];
1 int dp[maxn][maxn]; 2 void solve() 3 { 4 dp[0][0]=1; 5 for(int i=1;i<=m;i++){ 6 for(int j=0;j<=n;j++) 7 { 8 if(j-i>=0) 9 dp[i][j]=dp[i-1][j]+dp[i][j-i]; 10 else 11 dp[i][j]=dp[i-1][j]; 12 } 13 } 14 }
poj3280(区间dp)
题意:可以在任意位置增删字符，增删有不同代价，求能构成回文串的最小代价，题解说是取的是增加和删除的最小代价
分析:dp[i][j]表示i到j构成回文串的最小代价，如果s[i]=s[j]，那么dp[i][j]=dp[i+1][j-1]，若不想等，我们知道对于任何一个区间，增加和删除一个字符都不会对原有区间产生影响，所以只用求dp[i+1][j]和dp[i][j-1]当中的最小值即可。非常感谢夹克爷给我的耐心讲解，开始还不太理解这题
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 #include <vector> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <bitset> 10 #include <cmath> 11 #include <queue> 12 #include <stack> 13 using namespace std; 14 const int maxn=2020; 15 int dp[maxn][maxn]; 16 char s[maxn]; 17 int n,m; 18 int vis[30]; 19 int main() 20 { 21 while(cin>>n>>m) 22 { 23 cin>>s; 24 memset(dp,0,sizeof(dp)); 25 memset(vis,0,sizeof(vis)); 26 for(int i=0;i<n;i++) 27 { 28 char c; 29 int start,over; 30 cin>>c>>start>>over; 31 vis[c-'a']=min(start,over); 32 } 33 for(int i=m-1;i>=0;i--) 34 { 35 for(int j=i+1;j<m;j++) 36 { 37 if(s[i]==s[j]) 38 dp[i][j]=dp[i+1][j-1]; 39 else 40 dp[i][j]=min(dp[i+1][j]+vis[s[i]-'a'],dp[i][j-1]+vis[s[j]-'a']); 41 } 42 } 43 cout<<dp[0][m-1]<<endl; 44 } 45 return 0; 46 }
51nod 1092(区间dp)
最后再来一道一样的题目，不过更为简单，求最小添加多少字符可以构成回文串
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 #include <vector> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <bitset> 10 #include <cmath> 11 #include <queue> 12 #include <stack> 13 using namespace std; 14 const int maxn=1010; 15 char s[maxn]; 16 int dp[maxn][maxn]; 17 int n; 18 int main() 19 { 20 while(cin>>s) 21 { 22 memset(dp,0,sizeof(dp)); 23 n=strlen(s); 24 for(int i=n-1;i>=0;i--) 25 { 26 for(int j=i+1;j<n;j++) 27 { 28 if(s[i]==s[j]) 29 dp[i][j]=dp[i+1][j-1]; 30 else 31 dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1; 32 } 33 } 34 cout<<dp[0][n-1]<<endl; 35 } 36 return 0; 37 }