In the Set Covering problem, we are given a ground set $U$ and a collection $S$ of subsets of $U$, where each subset is associated with a non-negative cost, the Set Cover problem asks to find a minimum cost subcollection of $S$ that covers all elements in $U$. It is well known that the Set Covering problem is NP-hard.
Now my question is: Is the problem of finding a subcollection $A$ of $S$ that covers all elements in $U$ with minimum $\sum\limits_{i=1}^{|A|} |s_i| \cdot i$ (Here $|A|$ denotes the number of subsets in subcollection $A$, and $|s_i|$ denotes the number of elements in subset $s_i$. A is sorted in non-increasing order of $|s_i|$) still NP-hard. If so, how to prove it? Thanks in advance.
You can prove a problem is NP-hard by showing a polynomial time reduction of a known NP-hard problem to your problem. Observe that SET COVER can be reduced to your problem by padding out all the sets with duplicate elements so that they all have the same cardinality, which can be done in polynomial time. This is a polynomial many-one reduction from SET COVER to your problem, which proves that your problem is NP-hard.