Slash

思路:

观察数据范围和操作方式只能向右下,可以知道本题应该要使用朴素的三维$dp$.

状态定义:$dp[i][j][k]$:

第$(i,j)$格的字符$a_{i,j}$ 做第 $k$ 个字符的时候总体能够匹配的最长字符串.

注意由于每一格的格子需要有一个状态表示其不做字符串中的任何一个字符.
因此我们的$k$要从$0$开始取.

同时由于某一个格子的某一步还没有匹配完成和不存在这种匹配要区分开.

因此我们的$dp$数组需要初始化成$-1$,表示这种状态是不存在的.

而$dp[i][j][k] = 0$表示该状态在匹配但还未完全匹配完成.

AC Code:

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong() 
#define string() to_string()
#define Endl endl
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int n,m;
char a[110][110],s[110];
int dp[110][110][110];
void solve()
{
       cin>>n>>m;
       cin>>s+1;
       for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)cin>>a[i][j];

       memset(dp,-1,sizeof dp);//表示非法状态 和未完成的0状态做一个区分 
       int len=strlen(s+1);//步数 

       dp[0][1][0]=0;//初始化 和非法状态做一个区分
       for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
                for(int k=1;k<=len;k++)
                {
                        if(a[i][j]==s[k]&&dp[i-1][j][k-1]!=-1)dp[i][j][k]=dp[i-1][j][k-1]+(len==k);
                        if(a[i][j]==s[k]&&dp[i][j-1][k-1]!=-1)dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k-1]+(len==k));
                }
                dp[i][j][0]=dp[i][j][len];//完全用完 也不能和后面进行拼接
                for(int k=0;k<=len;k++)dp[i][j][0]=max({dp[i][j][0],dp[i-1][j][k],dp[i][j-1][k]});//前面的也需要转移过来
        }

        int ans=0;
        for(int i=0;i<=len;i++)ans=max(ans,dp[n][m][i]);
        cout<<ans<<Endl;
        return ;
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
     //   freopen("test.in","r",stdin);
        solve();
        return 0;
}

Traveling

思路:
构造题，注意细节。
考虑怎么样构造用的边数最少，然后如果$m$更大就加一些不影响任何最短路的边，如果两两连边还是不够$m$条就输出$No$。

首先考虑直接从1到n的最短路，显然必须有$d[1]=d[n]=min(d[i])$

怎么用最少的边来构造呢？首先将$2 \thicksim n-1$的所有点按权值排序.

顺着考虑这些点，如果$d[i] ≡ d[n] ( mod 2 )$

那么我们只需要添加一条$1$到$i$的边,边权为:$\Large \frac{d[i]-d[n]}{2}$.

比较麻烦的是: $d[i] \quad \not \equiv \quad d[n] \quad ( mod \quad 2 )$

考虑添加两条边，分别是连接$1$和$i$的边、连接$i$和$n$的边，边权如何确定？设两条边权分

别为$a$,$b$，我们希望走的路径是从$1$直接走到$i$再直接走到$n$，那么就不能出现从$1$走到

$n$再走到$i$，或者从$i$走到$1$再走到$n$的情况，为了保证这一点就需要$a + d[n] \ge b$ 以及 $b + d[n] \ge a$.

也就是 $\left \vert a - b \right \vert$尽可能的小,因此让${ a = \lfloor \large \frac {d[i]} {2} \rfloor } \quad$,$\ b = \lceil \frac {d[i]}{2} \rceil$

如果此时不满足 $d[i] + a \ge b$ 输出$No$

后续其他点面对同样局面和第一次面对该局面的点相连即可.

AC Code:

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong() 
#define string() to_string()
#define Endl endl
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
/*a+b<=2*a+d[n] <=> b<=a+d[n]
a+b<=d[n]+2*b <=> a<=b+d[n]
<=> b-a<=d[n] a-b<=d[n];

d[n]>=|b-a| */
int n,m;
struct node{
        int id,val;
        bool operator <(const node &a)const
        {
                return val<a.val;
        }
}d[N];
struct query{
        int u,v,val;
};
map<PII,bool>mp;
void solve()
{
       cin>>n>>m;
       int minv=inf;
       for(int i=1;i<=n;i++)cin>>d[i].val,d[i].id=i,minv=min(minv,d[i].val);
       if(n==1)
       {
               if(m==0&&d[n].val==0)
               {
                       cout<<"Yes"<<endl;
                       return ;
               }else 
               {
                       cout<<"No"<<endl;
                       return ;
               }
       }
       sort(d+2,d+n);//(2~n-1)升序排
       vector<query>ans;//双向边  
       if(d[n].val!=minv||d[1].val!=d[n].val||m>(ll)n*(n-1)/2)
       {
               cout<<"No"<<endl;
               return ;
       }
       if(m)ans.push_back({1,n,d[n].val}),mp[{1,n}]=true,m--;
       else
       {
               cout<<"No"<<endl;
               return ;
       }
       for(int i=2;i<=n-1;i++)
        if(d[i].val<minv)
        {
                cout<<"No"<<endl;
                return ;
        }
       int fa=-1,res=0;
       for(int i=2;i<=n-1;i++)
       {
          if(d[i].val%2==d[n].val%2)
          {
                  if(m==0)
                  {
                          cout<<"No"<<endl;
                          return ;
                  }
                  mp[{1,d[i].id}]=true;
                  ans.push_back({1,d[i].id,(d[i].val-d[n].val)/2});m--;
          }
          else
          {
                 if(fa==-1)
                 {
                       int a=d[i].val/2,b=(d[i].val+1)/2;
                       if(d[n].val+a>=b&&m>=2)
                       {
                             ans.push_back({1,d[i].id,a});mp[{1,d[i].id}]=true;
                             ans.push_back({d[i].id,n,b});mp[{d[i].id,n}]=true;
                             fa=d[i].id,res=d[i].val;m-=2;       
                       }else
                       {
                               cout<<"No"<<endl;
                               return ;
                       }
                 }else
                 {
                       if(m==0)
                       {
                               cout<<"No"<<endl;
                               return ;
                       }
                       ans.push_back({min(fa,d[i].id),max(fa,d[i].id),(d[i].val-res)/2});
                       mp[{min(fa,d[i].id),max(fa,d[i].id)}]=true;//标记那些边已经被用过了 
                       m--;
                 } 
          }
       }
       for(int i=1;i<=n;i++)
       {
               if(m==0)break;
               for(int j=i+1;j<=n;j++)
                if(!mp[{i,j}]&&m>0)ans.push_back({i,j,1000000000}),m--;
       }//处理 多出来的边 
       cout<<"Yes"<<endl;
       for(auto c:ans)cout<<c.u<<' '<<c.v<<' '<<c.val<<endl;
       return ;
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
      //  freopen("test.in","r",stdin);
        solve();
        return 0;
}