就是 bsp pla oot spl %d info pre 根据
今天考的题目都是 DP, 本来以为会有什么图论... 根据今天题目比较水的原因,我直接放解题报告,大家应该可以看得懂。。
- #include<stdio.h>
- #include<stdlib.h>
- #include<string.h>
- #include<math.h>
- using namespace std;
- const int maxn=10000+10,maxm=10010;
- #define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);
- int time[10010],x[10010],y[10010];
- int dp[maxm];
- int gi(){
- int sum=0,f=1;
- char ch=getchar();
- while(ch>'9' || ch<'0'){
- if(ch=='-')f=-1;
- ch=getchar();
- }
- while(ch<='9' && ch>='0'){
- sum=sum*10+ch-'0';
- ch=getchar();
- }
- return sum*f;
- }
- int max(int a,int b){
- if(a>b)return a;
- return b;
- }
- int can(int i,int j){
- if((abs(x[i]-x[j])+abs(y[i]-y[j]))<=time[i]-time[j])return 1;
- return 0;
- }
- int main(){
- file("dabai");
- int i,j,k,n,m,ans=0;
- n=gi();m=gi();
- for(i=1;i<=m;i++){
- time[i]=gi();x[i]=gi();y[i]=gi();
- dp[i]=1;
- for(j=1;j<i;j++)
- if(can(i,j))
- dp[i]=max(dp[i],dp[j]+1);
- ans=max(ans,dp[i]);
- }
- printf("%d\n",ans);
- return 0;
- }
T1
- #include < stdio.h > #include < stdlib.h > #include < string.h > #include < math.h > using namespace std;
- const int Mod = 1e9 + 7;#define file(a) freopen(a ".in", "r", stdin);
- freopen(a ".out", "w", stdout);
- int n;
- int dp[11];
- int a[11],
- b[11],
- ans;
- int max(int a, int b) {
- return a > b ? a: b;
- }
- int LIS() {
- int sum = 0;
- for (int i = 1; i <= n; i++) {
- dp[i] = 1;
- for (int j = 1; j < i; j++) if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
- sum = max(sum, dp[i]);
- }
- return sum;
- }
- void dfs(int i) {
- if (i > n) {
- int k = LIS();
- if (k <= 2) ans++;
- return;
- }
- for (int j = 1; j <= n; j++) if (!b[j]) {
- b[j] = 1;
- a[i] = j;
- dfs(i + 1);
- b[j] = 0;
- }
- }
- long long qsm(int a, int p) {
- long long cnt = 1;
- while (p) {
- if (p & 1) cnt = (cnt * a) % Mod;
- p >>= 1;
- a = (a * a) % Mod;
- }
- return cnt;
- }
- long long C[1010];
- long long inv[1010];
- int main() {
- file("repair");
- int i,
- j,
- k,
- m;
- scanf("%d", &n);
- inv[1] = 1;
- for (i = 2; i <= n + 1; i++) inv[i] = ((Mod - Mod / i) * (inv[Mod % i])) % Mod;
- /*
- dfs(1);
- O((n^2)*n!)
- */
- C[1] = 1;
- for (i = 2; i <= n; i++) C[i] = (((C[i - 1] * (4 * i - 2)) % Mod) * inv[i + 1]) % Mod;
- printf("%lld\n", C[n]);
- return 0;
- }
- /*
- 1432
- 2143
- 2413
- 2431
- 3142
- 3214
- 3241
- 3412
- 3421
- 4132
- 4213
- 4231
- 4312
- 4321
- */
T2
- #include<stdio.h>
- #include<stdlib.h>
- #include<string.h>
- #include<math.h>
- using namespace std;
- #define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);
- const int maxm=1000010,maxn=500000+10;
- struct node{
- int to,next,w;
- }e[maxm];
- int front[maxn],cnt;
- long long max(long long a,long long b){
- return a>b?a:b;
- }
- void Add(int u,int v,int w){
- e[++cnt].to=v;e[cnt].w=w;
- e[cnt].next=front[u];
- front[u]=cnt;
- }
- long long dis[maxn];
- int vis[maxn];
- void dfs1(int u){
- for(int i=front[u];i;i=e[i].next){
- int v=e[i].to;
- if(vis[v])continue;
- vis[v]=1;
- dfs1(v);
- vis[v]=0;
- dis[u]=max(dis[u],dis[v]+e[i].w);
- }
- }
- long long ans;
- void dfs(int u){
- for(int i=front[u];i;i=e[i].next)
- if(!vis[e[i].to]){
- vis[e[i].to]=1;
- dfs(e[i].to);
- int v=e[i].to;
- ans=ans+dis[u]-dis[v]-e[i].w;
- }
- }
- int main(){
- file("daodan");
- int i,j,k,n,m,root;
- scanf("%d",&n);
- scanf("%d",&root);
- for(i=1;i<=n;i++){
- int x,y,w;
- scanf("%d%d%d",&x,&y,&w);
- Add(x,y,w);Add(y,x,w);
- }
- vis[root]=1;
- dfs1(root);
- //for(i=1;i<=n;i++)
- // printf("%d:%d\n",i,dis[i]);
- memset(vis,0,sizeof(vis));
- vis[root]=1;
- dfs(root);
- printf("%lld\n",ans);
- return 0;
- }
T3
- #include<stdio.h>
- #include<stdlib.h>
- #include<string.h>
- #include<math.h>
- using namespace std;
- #define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);
- const int maxn=100000+10,maxm=200000+10;
- struct node{
- int to,next,w;
- }e[maxm];
- int front[maxn],cnt;
- void Add(int u,int v,int w){
- e[++cnt].next=front[u];
- front[u]=cnt;e[cnt].w=w;
- e[cnt].to=v;
- }
- int k,n;
- long long dp[maxn][110];
- long long min(long long a,long long b){
- return a<b?a:b;
- }
- long long max(long long a,long long b){
- return a>b?a:b;
- }
- long long dfs(int u,int fa,int K){
- if(dp[u][K])return dp[u][K];
- long long sum=0,cnt=0;
- for(int i=front[u];i;i=e[i].next){
- int v=e[i].to;
- if(v==fa)continue;
- if(!sum)sum=dfs(v,u,K)+e[i].w;
- else sum=max(sum,dfs(v,u,K)+e[i].w);
- if(K!=0){
- if(!cnt)cnt=dfs(v,u,K-1)+e[i].w;
- else cnt=min(cnt,dfs(v,u,K-1)+e[i].w);
- }
- }
- dp[u][K]=min(cnt,sum);
- return dp[u][K];
- }
- int main(){
- file("find");
- int i,j,m;
- scanf("%d%d%d",&n,&m,&k);
- for(i=1;i<=m;i++){
- int u,v,w;
- scanf("%d%d%d",&u,&v,&w);
- Add(u,v,w);
- }
- printf("%lld\n",dfs(1,-1,k));
- return 0;
- }
T4
今天考试最遗憾的就是所有题目都想出来了正解,但后面两题都是打萎了。。。
18.1.1 考试
来源: http://www.bubuko.com/infodetail-2447282.html