{purple9} {DP}
A Spy in the Metro
has_train那块搞了挺久的。。。
1 #include <cstdio> 2 #include <bits/stdc++.h> 3 using namespace std; 4 const int maxn=260; 5 const int INF=0x3f3f3f3f; 6 int t[maxn],curt; 7 int has_train[1500][55][2]; 8 int dp[220][55]; 9 int n,T,m1,m2; 10 11 int main() 12 { 13 int kase=0; 14 while(scanf("%d",&n)&&n) 15 { 16 memset(has_train,0,sizeof(has_train)); 17 scanf("%d",&T); 18 for(int i=0;i<n-1;i++) scanf("%d",&t[i]); 19 scanf("%d",&m1); 20 for(int i=0;i<m1;i++) 21 { 22 scanf("%d",&curt); 23 has_train[curt][0][0]=1; 24 for(int j=0;j<n-1;j++) { 25 curt+=t[j]; 26 has_train[curt][j+1][0]=1; 27 } 28 } 29 scanf("%d",&m2); 30 for(int i=0;i<m2;i++) 31 { 32 scanf("%d",&curt); 33 has_train[curt][n-1][1]=1; 34 for(int j=n-1;j>0;j--) { 35 curt+=t[j-1]; 36 has_train[curt][j-1][1]=1; 37 } 38 } 39 40 for(int i=0;i<n-1;i++) dp[T][i]=INF; 41 dp[T][n-1]=0; 42 43 for(int i=T-1;i>=0;i--) 44 for(int j=0;j<n;j++){ 45 dp[i][j]=dp[i+1][j]+1; //等待 46 if(j<n-1&&has_train[i][j][0]&&i+t[j]<=T) 47 dp[i][j]=min(dp[i][j],dp[i+t[j]][j+1]); //右 48 if(j>0&&has_train[i][j][1]&&i+t[j-1]<=T) 49 dp[i][j]=min(dp[i][j],dp[i+t[j-1]][j-1]); //左 50 } 51 printf("Case Number %d: ",++kase); 52 if(dp[0][0]>=INF) puts("impossible"); 53 else printf("%d ",dp[0][0]); 54 } 55 56 }
The Tower of Babylon
最长上升子序列
排序有点懵。。。
1 #include <cstdio> 2 #include <bits/stdc++.h> 3 using namespace std; 4 const int maxn=260; 5 const int INF=0x3f3f3f3f; 6 int dp[100]; 7 struct node 8 { 9 int a,b; 10 int h; 11 bool operator <(const node &x) 12 { 13 if(b!=x.b) return b>x.b; 14 else return a>x.a; 15 } 16 }sq[100]; 17 int cnt=0; 18 int n; 19 20 int main() 21 { 22 int kase=0; 23 while(scanf("%d",&n)&&n) 24 { 25 cnt=0; 26 for(int i=0;i<n;i++) 27 { 28 int a,b,h; 29 scanf("%d%d%d",&a,&b,&h); 30 sq[cnt++]={max(a,b),min(a,b),h}; 31 sq[cnt++]={max(a,h),min(a,h),b}; 32 sq[cnt++]={max(b,h),min(b,h),a}; 33 } 34 sort(sq,sq+cnt); 35 int ans=0; 36 for(int i=0;i<cnt;i++) 37 { 38 dp[i]=sq[i].h; 39 for(int j=0;j<i;j++) if(sq[i].a<sq[j].a&&sq[i].b<sq[j].b) 40 dp[i]=max(dp[i],dp[j]+sq[i].h); 41 ans=max(ans,dp[i]); 42 } 43 printf("Case %d: maximum height = %d ",++kase,ans); 44 } 45 46 }
Tour
lrjp269。题解链接
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn=1010; 4 double x[maxn],y[maxn]; 5 double dist[maxn][maxn]; 6 double dp[maxn][maxn]; 7 8 int main() 9 { 10 int n; 11 while(scanf("%d",&n)!=EOF) { 12 13 for(int i=1;i<=n;i++) { 14 scanf("%lf%lf",&x[i],&y[i]); 15 } 16 17 for(int i=1;i<=n;i++) { 18 for(int j=1;j<=n;j++) { 19 dist[i][j] = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); 20 } 21 } 22 23 for(int i=n-1;i>=2;i--) { 24 for(int j=1;j<i;j++) { 25 if(i==n-1) 26 dp[i][j] = dist[i][n] + dist[j][n]; 27 else dp[i][j] = min(dist[i][i+1]+dp[i+1][j],dist[j][i+1]+dp[i+1][i]); 28 } 29 } 30 printf("%.2lf ",dp[2][1]+dist[1][2]); 31 32 } 33 34 return 0; 35 }
Jin Ge Jin Qu hao
背包问题
注意题目给的数据可能是误导（过大），要分析实际数据可能大小。 // T<180*n+678<10000
要求首先是数目最多，其次才是时间最长。。。这块没注意WA了
1 #include <cstdio> 2 #include <bits/stdc++.h> 3 using namespace std; 4 int dp[10010],cnt[10010]; 5 int n,T,a; 6 7 int main() 8 { 9 int t,kase=0; 10 scanf("%d",&t); 11 while(t--) 12 { 13 memset(dp,0,sizeof(dp)); 14 memset(cnt,0,sizeof(cnt)); 15 scanf("%d%d",&n,&T); // T<180*n+678<10000!!! 16 for(int i=0;i<n;i++) 17 { 18 scanf("%d",&a); 19 for(int j=T;j>=a;j--) 20 if(cnt[j]<cnt[j-a]+1||cnt[j]==cnt[j-a]+1&&dp[j]<dp[j-a]+a) // 21 { 22 dp[j]=dp[j-a]+a; 23 cnt[j]=cnt[j-a]+1; 24 } 25 } 26 printf("Case %d: %d %d ",++kase,cnt[T-1]+1,dp[T-1]+678); 27 } 28 }
Partitioning by Palindromes
判断回文串的时候失了智。。。
1 #include <cstdio> 2 #include <bits/stdc++.h> 3 using namespace std; 4 const int maxn=1010; 5 bool s[maxn][maxn]; 6 char c[maxn]; 7 int d[maxn]; 8 int n; 9 10 int main() 11 { 12 scanf("%d",&n); 13 while(n--) 14 { 15 memset(s,0,sizeof(s)); 16 scanf("%s",c+1); 17 int len=strlen(c+1)+1; 18 for(int i=1;i<len;i++){ //=_=|| 19 d[i]=i; 20 for(int j=i;j>0;j--) 21 { 22 if(i==j) s[i][j]=true; 23 else if(i-j==1&&c[i]==c[j]) s[j][i]=true; 24 else if(s[j+1][i-1]&&c[i]==c[j]) s[j][i]=true; 25 else s[j][i]=false; 26 } 27 } 28 d[0]=0; 29 for(int i=1;i<len;i++) 30 for(int j=0;j<i;j++) 31 if(s[j+1][i]) d[i]=min(d[i],d[j]+1); 32 printf("%d ",d[len-1]); 33 } 34 35 }
Color Length
大概理解了写不出来代码。。。题解链接
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 using namespace std; 5 const int inf=0x3f3f3f3f; 6 const int maxn=5005; 7 char a[maxn],b[maxn]; 8 int len1,len2; 9 int first[255][3],last[255][3]; 10 int dp[maxn][maxn]; 11 int c[maxn][maxn]; 12 int main() 13 { 14 int T; 15 scanf("%d",&T); 16 for(int kase=1;kase<=T;++kase) 17 { 18 scanf("%s%s",a+1,b+1); 19 len1=strlen(a+1),len2=strlen(b+1); 20 for(int i='A';i<='Z';i++) 21 { 22 first[i][1]=first[i][2]=inf; 23 last[i][1]=last[i][2]=-1; 24 } 25 for(int i=0;i<=len1;i++) 26 for(int j=0;j<=len2;j++) 27 c[i][j]=dp[i][j]=0; 28 for(int i=1;i<=len1;i++) 29 { 30 if(first[a[i]][1]==inf) first[a[i]][1]=i; 31 last[a[i]][1]=i; 32 } 33 for(int i=1;i<=len2;i++) 34 { 35 if(first[b[i]][2]==inf) first[b[i]][2]=i; 36 last[b[i]][2]=i; 37 } 38 for(int i=0;i<=len1;i++) 39 { 40 if(i) 41 { 42 c[i][0]=c[i-1][0]; 43 if(first[a[i]][1]==i) c[i][0]++; 44 if(last[a[i]][1]==i&&last[a[i]][2]==-1) c[i][0]--; 45 } 46 for(int j=1;j<=len2;j++) 47 { 48 c[i][j]=c[i][j-1]; 49 if(first[b[j]][2]==j&&first[b[j]][1]>i) c[i][j]++; 50 if(last[b[j]][2]==j&&last[b[j]][1]<=i) c[i][j]--; 51 } 52 } 53 for(int i=0;i<=len1;i++) 54 for(int j=0;j<=len2;j++) 55 { 56 if(i>0&&j>0) dp[i][j]=min(dp[i-1][j],dp[i][j-1])+c[i][j]; 57 else if(i==0&&j>0) dp[i][j]=dp[i][j-1]+c[i][j]; 58 else if(i>0&&j==0) dp[i][j]=dp[i-1][j]+c[i][j]; 59 } 60 printf("%d ",dp[len1][len2]); 61 } 62 }
Another Crisis
UVA - 12186树dp
dfs，每个节点选择较小的k个子节点即可。
代码有误！！
1 #include <cstdio> 2 #include <bits/stdc++.h> 3 using namespace std; 4 const int maxn=100010; 5 6 struct edge 7 { 8 int v,nex; 9 }e[maxn]; 10 int head[maxn]; 11 int cnt,n,t; 12 void add(int u,int v) 13 { 14 e[cnt].v=v; 15 e[cnt].nex=head[u]; 16 head[u]=cnt++; 17 } 18 int dfs(int u) 19 { 20 int i=head[u]; 21 if(i==-1) return 1; //叶子 22 vector<int> v; 23 for(;i!=-1;i=e[i].nex) 24 { 25 v.push_back(dfs(e[i].v)); 26 } 27 int len=v.size(); 28 int k=(len*t/100)+(len*t%100==0?0:1); // 29 int temp=0; 30 sort(v.begin(),v.end()); 31 for(int j=0;j<k;j++) //选择较小的k个子节点 32 { 33 temp+=v[j]; 34 } 35 return temp; 36 } 37 int main() 38 { 39 while(scanf("%d%d",&n,&t)&&(n||t)) 40 { 41 cnt=0; 42 memset(head,-1,sizeof(head)); 43 for(int i=1;i<=n;i++) 44 { 45 int u; 46 scanf("%d",&u); 47 add(u,i); 48 } 49 printf("%d ",dfs(0)); 50 } 51 return 0; 52 }
Party at Hali-Bula
树dp
树的最大独立集，并判断是否唯一。
d[u][1]表示选u，d[u][0]表示不选u
f[u][1]==1表示选u的情况下唯一，f[u][1]==0表示不唯一
f[u][0]为不选u的情况下的唯一性
没仔细读题，，Yes和No输反了=_=||
1 #include <cstdio> 2 #include <bits/stdc++.h> 3 using namespace std; 4 const int maxn=220; 5 map<string,int> m; 6 int n; 7 struct edge 8 { 9 int v; 10 int nex; 11 }e[maxn]; 12 int head[maxn]; 13 int cnt=0; 14 void add(int u,int v) 15 { 16 e[cnt].v=v; 17 e[cnt].nex=head[u]; 18 head[u]=cnt++; 19 } 20 string s1,s2; 21 int d[maxn][2],f[maxn][2]; 22 void dfs(int u) 23 { 24 f[u][1]=f[u][0]=1; 25 for(int i=head[u];i!=-1;i=e[i].nex) 26 { 27 int v=e[i].v; 28 dfs(v); 29 d[u][0]+=max(d[v][1],d[v][0]); 30 d[u][1]+=d[v][0]; 31 if(f[v][0]==0) f[u][1]=0; 32 //下面分三种情况判断f[u][0] 33 if(d[v][1]==d[v][0]) f[u][0]=0; 34 if(d[v][1]>d[v][0]&&f[v][1]==0) f[u][0]=0; 35 if(d[v][0]>d[v][1]&&f[v][0]==0) f[u][0]=0; 36 } 37 d[u][1]++; 38 return ; 39 } 40 int main() 41 { 42 while(scanf("%d",&n)&&n) 43 { 44 m.clear(); 45 int id=2; 46 cnt=0; 47 memset(head,-1,sizeof(head)); 48 memset(d,0,sizeof(d)); 49 memset(f,0,sizeof(f)); 50 cin>>s1; 51 m[s1]=1; 52 for(int i=1;i<n;i++) 53 { 54 cin>>s1>>s2; 55 if(!m[s1]) m[s1]=id++; 56 if(!m[s2]) m[s2]=id++; 57 add(m[s2],m[s1]); 58 } 59 dfs(1); 60 int ans,flag=1; 61 if(d[1][1]>d[1][0]) 62 { 63 ans=d[1][1]; 64 if(f[1][1]) flag=1; 65 else flag=0; 66 } 67 else if(d[1][1]<d[1][0]) 68 { 69 ans=d[1][0]; 70 if(f[1][0]) flag=1; 71 else flag=0; 72 } 73 else ans=d[1][1],flag=0; 74 printf("%d %s ",ans,flag?"Yes":"No"); 75 } 76 return 0; 77 }
Perfect Service
树dp
第三个状态转移公式不会，难理解。。。
有些细节做的不好。。。
1 #include <cstdio> 2 #include <bits/stdc++.h> 3 using namespace std; 4 const int maxn=10010; 5 int d[maxn][3]; 6 int in[maxn]; 7 struct edge 8 { 9 int v,nex; 10 }e[maxn<<1]; 11 int head[maxn]; 12 int cnt; 13 void add(int u,int v) 14 { 15 e[cnt].v=v; 16 e[cnt].nex=head[u]; 17 head[u]=cnt++; 18 } 19 int n; 20 void dfs(int u,int f) 21 { 22 d[u][2]=10000; //!!!不合法 23 d[u][0]=1; 24 d[u][1]=0; 25 for(int i=head[u];i!=-1;i=e[i].nex) 26 { 27 28 int v=e[i].v; 29 if(v==f) continue; 30 dfs(v,u); 31 d[u][0]+=min(d[v][0],d[v][1]); 32 d[u][1]+=d[v][2]; 33 d[u][2]=min(d[u][2],d[u][1]-d[v][2]+d[v][0]); 34 } 35 return ; 36 } 37 int main() 38 { 39 int u,v; 40 while(scanf("%d",&n)&&n!=-1) 41 { 42 cnt=0; 43 memset(head,-1,sizeof(head)); 44 memset(d,0,sizeof(d)); 45 memset(in,0,sizeof(in)); 46 for(int i=1;i<n;i++) 47 { 48 scanf("%d%d",&u,&v); 49 add(u,v); 50 add(v,u); 51 } 52 dfs(1,0); 53 printf("%d ",min(d[1][0],d[1][2])); 54 scanf("%d",&u); 55 if(u==0) continue; 56 else break; 57 } 58 }
Headmaster's Headache
状压dp
m和n输入反了一直WA也是很懵比，对着lrj代码找了好久都没发现。。。
1 #include <cstdio> 2 #include <bits/stdc++.h> 3 using namespace std; 4 const int INF= 0x3f3f3f3f; 5 const int maxn=125; 6 const int maxx=8; 7 int m,n,s; 8 int c[maxn],st[maxn],d[maxn][1<<maxx][1<<maxx]; 9 10 int dp(int i,int s0,int s1,int s2) 11 { 12 if(i==m+n) return s2==(1<<s)-1 ? 0 : INF; 13 int &ans=d[i][s1][s2]; 14 if(ans>=0) return ans; 15 ans=INF; 16 if(i>=m) ans=dp(i+1,s0,s1,s2); //不选 17 int m0=st[i]&s0; 18 int m1=st[i]&s1; 19 s0^=m0; 20 s1=(s1^m1)|m0; 21 s2|=m1; 22 ans=min(ans,c[i]+dp(i+1,s0,s1,s2)); //选 23 return ans; 24 } 25 int main() 26 { 27 while(scanf("%d%d%d",&s,&m,&n)&&(s||m||n)) 28 { 29 memset(d,-1,sizeof(d)); 30 getchar(); 31 for(int i=0;i<m+n;i++) 32 { 33 st[i]=0; 34 string line; 35 int x; 36 getline(cin,line); 37 stringstream ss(line); 38 ss>>c[i]; 39 while(ss>>x) 40 { 41 x--; 42 st[i]|=(1<<x); 43 } 44 // cout<<"能教的科目为： "; 45 //for(int j=0;j<s;j++) if(st[i]&(1<<j)) cout<<j+1<<' '; 46 //cout<<endl; 47 } 48 printf("%d ",dp(0,(1<<s)-1,0,0)); 49 } 50 return 0; 51 52 }
Twenty Questions
状压dp
自己不会写啊。。。
d[s][a]表示已经问了s中为1的位置，状态为a时最少还需要问几次
（简言之s保存的是询问过的位置。。。）
【我们每次把物品中已经询问的位置（即s为1的那些位置）都和状态a一致的选出来，如果只有一个，说明我们已经找到，否则，继续询问备选缩小范围。】
a是不确定的，每次决策a的那个位置可能是0或1，我们要求的是不管那位0或者1，都可以唯一确定a最少还要问的次数，即两种状态下取较大的次数。
要求最优决策下的最小次数，每次决策更新最小值ans。
当所有物品中满足a的个数等于1时，得到一个次数返回比较即可。
1 #include <cstdio> 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 const int maxn = 1 << 12; 6 const int INF = 0x3f3f3f3f; 7 8 string str; 9 int w[130]; 10 int d[maxn][maxn]; 11 int m, n; 12 13 int dp(int s, int a) 14 { 15 int& ans = d[s][a]; 16 if (ans != INF) return ans; 17 int cnt = 0; 18 for (int i = 0; i<n; i++) 19 //边界条件判断，如果cnt<=1，则说明能判断出来了 20 if ((w[i] & s) == a) cnt++; 21 if (cnt <= 1){ d[s][a] = 0; return 0; } 22 23 for (int i = 0; i<m; i++) 24 { 25 if (s&(1 << i))continue; 26 ans = min(ans, max(dp(s | 1 << i, a | 1 << i), dp(s | 1 << i, a)) + 1); 27 } 28 return ans; 29 } 30 31 int main() 32 { 33 while (cin>>m>>n &&n&&m) 34 { 35 memset(w, 0, sizeof(w)); 36 memset(d, INF, sizeof(d)); 37 for (int i = 0; i<n; i++) 38 { 39 cin >> str; 40 for (int j = 0; str[j]; j++) 41 if (str[j] == '1') w[i] |= (1 << j); 42 } 43 printf("%d ", dp(0,0)); 44 } 45 }
Dropping water balloons
可以说是很懵比了。。。
和上一个题有相似之处，就是我们需要判断的结果是一个未知量。如本题气球的硬度，可能为1，2，3，------，n，n+1。
最坏情况需要测到n楼才知道结果。题目要求确定气球硬度，我们要考虑所有情况。【即我们要求的是最少测几次才可以测到n楼。】
用d[i][j]表示i个气球j次试验最多测到d[i][j]楼（即运气足够好的情况下可以测到几层楼）【这也是题目要求的，最少几次！！】
（上面这两条红字放一起有点难以理解）
我们首先要求的是第一次最好在哪一层楼进行测试
先设第一次为k楼最好（以下八行都是在这个假设下进行的，记为假设一吧）
如果第一次气球就破，则说明i-1个气球j-1次试验测（即d[i-1][j-1]）需要测到k-1层楼才可以，即d[i-1][j-1]==k-1。证明如下：
反证法：
假设d[i-1][j-1]=x<k-1，则x楼到k楼之间是断层，说明第一次测试的k楼没有意义，k不是最好，与假设一矛盾，故d[i-1][j-1]>=k-1
假设d[i-1][j-1]=x>k-1，即d[i-1][j-1]>=k，说明i-1个气球j-1次就可以测到k+层楼了，第一次测试的k层楼没有意义，k不是最好，与假设一矛盾，故d[i-1][j-1]<=k-1
综上，d[i-1][j-1]==k-1。
即i个气球j次试验第一次最好在k=d[i-1][j-1]+1楼进行测试
同时这也是第一次气球就破的情况下最多可以测到的楼层数d[i][j]=k=d[i-1][j-1]+1。
如果第一次气球不破，那么我们还剩下i个气球j-1次试验，最多可以再测d[i][j-1]层楼（要仔细考虑，和高度无关）,再加上之前的k楼
即第一次气球不破的情况下最多可以测到的楼层数d[i][j]=d[i][j-1]+k=d[i][j-1]+d[i-1][j-1]+1。
所以，综上分析，i个气球j次试验最多可以测到d[i][j]=d[i][j-1]+k=d[i][j-1]+d[i-1][j-1]+1。
现在回到题目，【即我们要求的是最少测几次才可以测到n楼。】
根据递推公式预处理d[i][j]表。
气球数目为k，楼层为n，只需枚举次数j，当d[k][j]>=n时j即为所求解。
1 #include <cstdio> 2 #include <bits/stdc++.h> 3 using namespace std; 4 #define LL long long 5 LL f[110][65]; 6 int k; 7 LL n; 8 9 int main() 10 { 11 memset(f,0,sizeof(f)); 12 for(int i=1;i<=100;i++) 13 for(int j=1;j<64;j++) 14 f[i][j]=f[i-1][j-1]+1+f[i][j-1]; 15 while(scanf("%d%lld",&k,&n)&&k) 16 { 17 if(f[k][63]<n) 18 { 19 puts("More than 63 trials needed."); 20 continue; 21 } 22 for(int i=1;i<=63;i++) if(f[k][i]>=n) 23 { 24 printf("%d ",i); 25 break; 26 } 27 } 28 return 0; 29 }
Team them up!
UVA - 1627虽然只是个01背包，二分图。。。还是不会写，看起来都费劲。。。
以后再回来看吧-_-||
刚刚又去学习了下背包问题九讲，有些东西豁然开朗的感觉。。。
贴个链接吧http://love-oriented.com/pack/P09.html
首先是dp里面初始时，d[0][0+n]=1,这是当前一个组也没选的合法状态，差额为本来为0。但是考虑到差额可能为负值，故加上n，因此以下dp的差额全部加了n。
输出时，因为是dp时是从第一个连通块到最后一个连通块，所以输出时从后往前递推输出结果。
1 // UVa1627 Team them up! 2 // Rujia Liu 3 #include<cstdio> 4 #include<cstring> 5 #include<iostream> 6 #include<vector> 7 #include<algorithm> 8 using namespace std; 9 10 const int maxn = 100 + 5; 11 12 int n, G[maxn][maxn], color[maxn], diff[maxn], cc; 13 vector<int> team[maxn][2]; // team[cc][c] is the list of people in connected-component cc, color c 14 15 // returns false if not bipartite graph 16 bool dfs(int u, int c) { 17 color[u] = c; 18 team[cc][c-1].push_back(u); 19 for(int v = 0; v < n; v++) {//实际只能通过不满足联接的条件，来确定另外一个队的点集 20 if(u != v && !(G[u][v] && G[v][u])) { // u and v must be in different groups 21 if(color[v] > 0 && color[v] == color[u]) return false; 22 if(!color[v] && !dfs(v, 3-c)) return false; 23 } 24 } 25 return true; 26 } 27 28 bool build_graph() { 29 memset(color, 0, sizeof(color)); 30 cc = 0; // current connected-component 31 for(int i = 0; i < n; i++) 32 if(!color[i]) { 33 team[cc][0].clear(); 34 team[cc][1].clear(); 35 if(!dfs(i, 1)) return false; //可以保证color[i]为0时，设i为1队并不与已有条件冲突 36 diff[cc] = team[cc][0].size() - team[cc][1].size(); 37 cc++; 38 } 39 40 return true; 41 } 42 43 // d[i][j+n] = 1 iff we can arrange first i cc so that team 1 has j more people than team 2. 44 int d[maxn][maxn*2], teamno[maxn]; 45 46 void print(int ans) { 47 vector<int> team1, team2; 48 for(int i = cc-1; i >= 0; i--) { 49 int t; 50 if(d[i][ans-diff[i]+n]) { t = 0; ans -= diff[i]; } 51 else { t = 1; ans += diff[i]; } 52 for(int j = 0; j < team[i][t].size(); j++) 53 team1.push_back(team[i][t][j]); 54 for(int j = 0; j < team[i][1^t].size(); j++) 55 team2.push_back(team[i][1^t][j]); 56 } 57 printf("%d", team1.size()); 58 for(int i = 0; i < team1.size(); i++) printf(" %d", team1[i]+1); 59 printf(" "); 60 61 printf("%d", team2.size()); 62 for(int i = 0; i < team2.size(); i++) printf(" %d", team2[i]+1); 63 printf(" "); 64 } 65 66 void dp() { 67 memset(d, 0, sizeof(d)); 68 d[0][0+n] = 1; 69 for(int i = 0; i < cc; i++) 70 for(int j = -n; j <= n; j++) if(d[i][j+n]) { 71 d[i+1][j+diff[i]+n] = 1; 72 d[i+1][j-diff[i]+n] = 1; 73 } 74 //每一次安排（即cc++），都是通过目前与所有的其他点的安排没有冲突的点来生成的，所以不论+diff[i]或-diff[i]都没问题 75 76 for(int ans = 0; ans <= n; ans++) { 77 if(d[cc][ans+n]) { print(ans); return; } 78 if(d[cc][-ans+n]) { print(-ans); return; } 79 } 80 } 81 82 int main() { 83 int T; 84 cin >> T; 85 while(T--) { 86 cin >> n; 87 memset(G, 0, sizeof(G)); 88 for(int u = 0; u < n; u++) { 89 int v; 90 while(cin >> v && v) G[u][v-1] = 1; 91 } 92 93 if(n == 1 || !build_graph()) cout << "No solution "; 94 else dp(); 95 96 if(T) cout << " "; 97 } 98 return 0; 99 }
Fixing the Great Wall
区间dp
还是看的别人代码，其实这个题不难，被前几道搞得有心理阴影了。。。
有一个细节，输入不加！=EOF的话会超时（虽然题目说了以00结束）
1 #include <cstdio> 2 #include <bits/stdc++.h> 3 using namespace std; 4 const int maxn=1005; 5 struct node 6 { 7 int pos,c,d; 8 node(int pos=0,int c=0,int d=0):pos(pos),c(c),d(d){} 9 bool operator <(const node &x) const 10 { 11 return pos<x.pos; 12 } 13 }p[maxn]; 14 int sum[maxn]; 15 double dp[maxn][maxn][2]; 16 17 int main() 18 { 19 int n,v,fp; 20 while(scanf("%d%d%d",&n,&v,&fp)!=EOF&&(n||v||fp)) 21 { 22 for(int i=0;i<n;i++) 23 scanf("%d%d%d",&p[i].pos,&p[i].c,&p[i].d); 24 p[n].pos=fp;p[n].c=0;p[n].d=0; 25 sort(p,p+n+1); 26 int w=lower_bound(p,p+n+1,node(fp,0,0))-p; 27 sum[0]=p[0].d; 28 for(int i=1;i<=n;i++) sum[i]=sum[i-1]+p[i].d; 29 //memset(dp,0x3f3f3f3f,sizeof(dp)); 30 for(int i=0;i<=n;i++) 31 for(int j=i;j<=n;j++) dp[i][j][0]=dp[i][j][1]=0x3f3f3f3f; 32 dp[w][w][0]=dp[w][w][1]=0; 33 for(int i=w;i>=0;i--) 34 for(int j=w;j<=n;j++) 35 { 36 double ss=sum[i-1]+sum[n]-sum[j]; 37 if(i!=0) //往左 38 { 39 //从左到左 40 double t=1.0*(p[i].pos-p[i-1].pos)/v; 41 dp[i-1][j][0]=min(dp[i-1][j][0],dp[i][j][0]+p[i-1].c+t*ss); 42 //从右到左 43 t=1.0*(p[j].pos-p[i-1].pos)/v; 44 dp[i-1][j][0]=min(dp[i-1][j][0],dp[i][j][1]+p[i-1].c+t*ss); 45 } 46 if(j!=n) //往右 47 { 48 //从右到右 49 double t=1.0*(p[j+1].pos-p[j].pos)/v; 50 dp[i][j+1][1]=min(dp[i][j+1][1],dp[i][j][1]+p[j+1].c+ss*t); 51 //从左到右 52 t=1.0*(p[j+1].pos-p[i].pos)/v; 53 dp[i][j+1][1]=min(dp[i][j+1][1],dp[i][j][0]+p[j+1].c+ss*t); 54 } 55 } 56 int ans=min(dp[0][n][0],dp[0][n][1]); 57 printf("%d ",ans); 58 } 59 return 0; 60 }
感觉后面的DP做不动了，先放放吧。。。等一阵再回来接着做。。。